Formally, a Boolean circuit \( B \) is a directed acyclic graph whose nodes can include conjunctions (\( \wedge \): logical ANDs), disjunctions (\( \vee \): logical ORs), negations ( \( \neg \): logical NOTs), and literal leaves. As we saw last time, negation nodes can be all shifted down to the bottom level by De Morgan’s law to become a De Morgan circuit:
So, a leaf of \( B \) represents either a positive literal (i.e. just an input variable to the entire logical formula, or Boolean function computed by \(B\)), or a negative literal (negated variable). In the same example as the last time:
the Boolean function computed by this \(B\) is \( f_\alpha = ( (1,2) \vee (1,3) ) \wedge ( (1,3) \vee \neg (1,2)) \). It’s concerned with the existence of just the two edges (1, 2) and (1,3) in the graph of the three vertices {1, 2, 3}, returning true if and only if the formula is true.
We can expand \( f_\alpha \) into its disjunctive normal form (DNF) by the distributive law. Think of \( \wedge \) as the multiplication and \( \vee \) as an addition to expand it as much as you can. Then you see something similar to \( DNF(\alpha) \) shown in the figure, i.e. \( f_\alpha = ( (1, 2) \wedge (1,3) ) \vee ( (1,2) \wedge \neg (1,2) ) \vee \cdots \). Now the two logical symbols have become redundant so it’s efficient to drop them as in the figure, i.e., \( DNF(\alpha) \) is a collection (family) of sets of literals. Each literal set in there is called term. When any term is true, it sets the whole \( f_\alpha \) true. Some of them can never be positive containing a contradiction (i.e., both an edge and its negation) such as the second term in \( DNF(\alpha) \).
Now there is a Boolean function of big interest:
$$
\bigvee_{C \in {[n] \choose m}} \bigwedge_{E \in {C \choose 2}} E.
$$
Here \( [n] = \{ 1, 2, 3, …., n \} \) represents the set of \( n \) vertices in a given general graph, and \( { \textrm{set} S \choose m }\) means the family of all subsets of the given set \( S \), each of cardinality \( m\) – let’s call such a set \( m \)-set for short.
So \( \bigvee_{C \in {[n] \choose m}} \) considers all the \( m \)-vertex sets \( C \), combining the following logical formulas with respect to \( C \) by OR. Also \( \bigwedge_{E \in {C \choose 2}} E \) for each \( C \) takes all its 2-subsets – they are the edges of \( C \) ! – to combine them by AND regarding \( E \) as positive literals. So, the Boolean function returns True if and only if the given graph includes a clique of size \( m \), i.e., an \( m \)-vertex set filled with every single possible edge. The function is hence called the clique function.
If you could show a general way to build a Boolean circuit to compute the clique function of any \( n \) with \( < n^c \) (polynomial) nodes, the P vs NP problem would be solved with \( P = NP \). If you could show that there’s no way to build such a Boolean circuit for any given \( n \), this would solve the problem with \( P \ne NP \). But no one has done it either way after many years of investigation.
The clique function is a monotone Boolean function, i.e., all the literals are positive because they are all edges \( E \). This hardly means a Boolean circuit to compute the clique function should be monotone as well: such a circuit for simple examples contains many negative literals – we see these much later in this blog series noting their significance.
We can show that a monotone circuit without a negative literal cannot compute the clique function well: any of them would be too big with exponentially many nodes. Its standard proof is given in computer science textbooks using sunflowers. I’ll explain it in Chap 6 of this series too.
We’ll focus on sunflowers starting next time.
Links for mobile devices
- Index page
- Paper 1 Ver 1 (It has a major error that I am trying to fix now.)