Use a Boolean circuit of unbounded-fan-in AND and OR gates, with negations pushed to the input Boolean literals. Its circuit depth is the largest number of AND/OR gates on an input-to-output path, and its circuit size counts these gates. Constants and Boolean literals may be supplied as inputs. Equivalent standard size conventions only enlarge the absolute constants. One can merge adjacent gates of the same type; the depth-reduction argument below keeps the two possible normal forms available at each gate.
A random restriction with parameter independently leaves each variable live with probability and otherwise fixes it to zero or one with probability each. The Håstad switching lemma states that for a width- DNF or conjunctive normal form ,
Width bounds Boolean literals in a term or clause, not the number of terms. A decision tree of depth at most has both a DNF and a conjunctive normal form of width at most and has real multilinear degree at most . Indeed every leaf condition is a product of at most factors or ; sum the accepting leaves. The switching lemma controls the canonical decision tree, hence implies this representation bound.
We detail the Boolean circuit simplification parameters. First use a -random restriction. For a bottom AND gate, let count its live Boolean literals on the event that no fixed Boolean literal kills it. For distinct Boolean literals,
Thus the probability of retaining more than live Boolean literals without becoming constant is at most . The same calculation applies to bottom OR gates, with the opposite killing value. Repeated Boolean literals are removed and contradictory Boolean literals make a constant gate. A union bound makes all nonconstant bottom gates width at most , except with probability at most .
Now apply successive restrictions, each retaining probability of the remaining variables. At a two-layer gate, the current bottom forms are width- DNFs or conjunctive normal forms. The Håstad switching lemma bounds its probability of failing to reduce to decision-tree depth at most by . Convert the successful decision tree into the opposite normal form, whose terms or clauses have width at most , and merge its outer gate with the adjacent gate of the same type. This removes one layer. Repeat upwards until the output has a depth- decision tree.
The bookkeeping matters: although a decision tree may give clauses, each subsequent switching event is charged to the corresponding original Boolean circuit gate, not to each newly created clause. The lemma permits any number of terms. Each original gate is charged once, so the sum of the failure probabilities is at most , without an extra exponential size factor. Conditioning on successful preceding stages is harmless because each next restriction is fresh and the width bound holds for every preceding success. For a general Boolean circuit the conjunctive normal form or DNF representation at a shared gate can be chosen separately for each outgoing use; no extra gates need to be counted as switching targets.
The composed restriction has live-variable probability
Fixed values are still unbiased and coordinates independent. We have proved the useful intermediate estimate
For , the initial bottom-gate argument alone gives this conclusion. This is a depth-reduction estimate, not the desired Fourier-tail theorem used as a black box.
Next derive exactly how restrictions affect the Fourier-Walsh transform. Let be the random live set and the fixed assignment outside . With , the restricted coefficient at is
Orthogonality of the fixed-coordinate characters eliminates cross terms after averaging over . Therefore
and then averaging over gives the expected Fourier weight after a random restriction identity
The original high-degree tail is not preserved: each original coefficient is weighted by a binomial distribution survival probability. On successful restrictions the left-hand tail vanishes; on failures it is at most one by Parseval's identity and . Hence its expectation is at most .
Put . If , choose and the preceding value of . For every , the binomial distribution mean satisfies
Its variance is at most . The Chebyshev inequality gives
Thus the exact expectation identity bounds at least half the original tail above , and
When the same bound follows from the trivial total-weight bound . We obtain explicit absolute constants,
This supplies the requested overview of the Linial-Mansour-Nisan theorem with the actual switching scale, gate-count bookkeeping and restriction-to-Fourier calculation. The argument uses the unbounded-fan-in AND/OR Boolean circuit basis; allowing arbitrary gates would make the theorem false, since one parity gate could have all its nonconstant Fourier weight at level . The original theorem is Linial, Mansour and Nisan's circuit Fourier bound.
The Cook-Levin theorem states that the Boolean satisfiability problem is NP-complete under polynomial-time many-one reductions. Membership in NP follows by guessing an assignment and evaluating the formula in time polynomial in its description length.
For hardness, let have a deterministic polynomial-time verifier , with a polynomial witness-length bound. Use a fixed polynomial certificate length: a short certificate is encoded by its length followed by padded data, and the verifier checks this encoding. Pad the computation to exactly steps, with accepting and rejecting states absorbing. Enlarge polynomially if necessary to cover input/witness initialization. A standard polynomial slowdown permits a single-tape Turing machine, so it suffices to handle that model.
Encode a tape cell by a fixed number of bits recording its alphabet symbol and either no head or the head's finite control state. Starting with one head, a cell's next label depends only on its own label and the two neighboring labels: a head can change the symbol where it sits and can enter only a neighbor. Each such finite local function has a constant-size Boolean circuit. The initial row fixes , blanks and the starting head, leaving only the witness bits as Boolean circuit inputs. There are relevant cells with blank margins beyond every possible head position, and updates. Repeating these local Boolean circuits produces a Boolean circuit of size , with an output detecting an accepting head in the final row. The construction is computable in polynomial time. Induction on rows shows that every assignment to produces exactly the verifier's valid computation; invalid local encodings can be assigned arbitrary Boolean circuit behavior because they never arise from the valid initial row.
Convert this Boolean circuit to conjunctive normal form using a Tseitin transformation. Introduce one variable for each wire, and encode each gate output by:
Gate relationClauses imposing equivalence
Unit clauses fix constant sources and assert the final output. Each input assignment has exactly one extension to its gate values, so the resulting formula is satisfiable precisely when some witness makes accept. It has clauses of bounded length and is produced in polynomial time. Thus
This proof also gives hardness for clauses of at most three literals, without needing a separate satisfiability assumption.
The given logical implication is false exactly when and . For every literal on , there is such a false Boolean valuation making that literal true. For a prescribed value of or , give the other the same value and choose . For a prescribed value of or , give the other the opposite value and choose .
Consequently no literal implies the whole propositional formula: there is no one-literal implicant. If an equivalent disjunctive normal form contained a one-literal conjunction term , then every Boolean valuation satisfying would satisfy that disjunctive normal form, contradicting its equivalence to the given propositional formula. This proves the claim. Even if auxiliary Boolean variables are allowed in the equivalent expression, a one-literal term on one of them fails too: fix any false Boolean valuation of the original four and set the auxiliary literal true. The word “conjunct” here refers to a conjunction term in the disjunctive normal form, not a factor in a conjunctive normal form.
Use and for false and true truth values. The truth table is:
The two satisfying rows with combine by eliminating , while the remaining satisfying row has . An equivalent disjunctive normal form is therefore
Expanding the logical biconditional into its two implications, and using , gives the conjunctive normal form
Each form has exactly the same three satisfying assignments as the original propositional formula.