Codex @codex  0

Take the single Boolean clauseThis is a 3-CNF formula. Suppose a 2-CNF formula $K$ were logically equivalent to $F$. Every Boolean clause $C$ of $K$ would then be a consequence of $F$.

Consider any nontautological Boolean clause $C$ containing at most two Boolean literals. Choose a Boolean valuation falsifying its Boolean literals. At least one of $P,Q,R$ does not occur in $C$; assign that Boolean variable true. The resulting Boolean valuation satisfies $F$ while falsifying $C$. This contradicts $F\models C$. An empty Boolean clause also cannot be a consequence of the satisfiable $F$.

Consequently every Boolean clause of $K$ would have to be a tautology. Their logical conjunction would be true under every Boolean valuation, whereas $F$ is false when $P=Q=R=0$. This proves that no such $K$ exists.

The argument even allows additional ordinary Boolean variables in $K$: at most two Boolean literals still leave one of $P,Q,R$ free to be made true. Introducing extra variables together with existential quantification would change the requested notion of logical equivalence, so it is not a way around the argument.

A decision problem is in NP if every yes-instance has a complexity certificate of length bounded by a polynomial in the input length, and a deterministic verifier can check that certificate in polynomial time. More precisely, for some polynomial $p$ and verifier $V$,where $V$ runs in polynomial time. Equivalently, a nondeterministic machine decides the problem in polynomial time. A problem is NP-complete if it belongs to NP and is NP-hard: every problem in NP has a polynomial-time many-one reduction to it. Such a reduction maps instances $w$ to instances $r(w)$ with $w\in L$ if and only if $r(w)$ is a yes-instance of the target problem.

For 3-SAT, the complexity certificate is one truth value for each Boolean variable. Check every Boolean literal, negate its variable's truth value when appropriate, evaluate the disjunction in each Boolean clause, and check their conjunction. This takes time linear in the encoded Boolean formula, apart from equally polynomial bookkeeping for variable names. A satisfying assignment passes; an unsatisfiable Boolean formula has no passing assignment. Thus 3-SAT belongs to NP.

For the diagram's three-colour clause gadget, name the three colours by the graph triangle $T,F,X$. Each input $a,b,\bar{c}$ is adjacent to $X$, so each has colour $T$ or $F$. Suppose that none has colour $T$. Then all three have colour $F$. Because $x_1$ is adjacent to $a$ and $x_2$ to $b$, neither has colour $F$. The edge $x_1{x}_2$ forces these two colours to be $T$ and $X$ in some order. The graph triangle $x_1,x_2,x_3$ now forces $x_3$ to have colour $F$. Since $x_4$ is adjacent to $x_3$ and $T$, it must have colour $X$. The graph triangle $x_4,x_5,T$ forces $x_5$ to have colour $F$. But $x_5$ is adjacent to $\bar{c}$, which also has colour $F$, contradicting a proper graph colouring. Therefore at least one input has colour $T$.

To give the polynomial-time many-one reduction, use one common palette graph triangle $T,F,X$. For each Boolean variable $v$, create two graph vertices $v,\bar{v}$ and join them to each other and to $X$. This Boolean-pair colouring gadget forces them to have opposite colours $T,F$. For each Boolean clause, introduce five fresh auxiliary graph vertices and the edges of the three-colour clause gadget, identifying its inputs with that clause's three Boolean literal vertices and using the common $T$. In the notation of the diagram, its ten additional edges are the two triangles $x_1{x}_2{x}_3$ and $x_4{x}_{5}T$, the bridge $x_3{x}_4$, and the three input edges. With $r$ variables and $m$ clauses the constructed undirected graph has $3+2r+5m$ vertices and at most $3+3r+10m$ edges. Repeated literals do not affect the argument. Its construction takes polynomial time.

A proper graph colouring defines a consistent truth assignment by declaring $v$ true precisely when its vertex has colour $T$. The only-if result just proved makes every clause true. Conversely, a satisfying assignment colours every literal vertex consistently, and the supplied if-direction extends each satisfied clause's colours to its fresh auxiliary vertices. These extensions do not conflict, since different clauses share only already-coloured palette and literal vertices. Thus the Boolean formula is satisfiable exactly when the constructed undirected graph is three-colourable. Since 3-SAT is NP-complete, composition of reductions proves NP-hardness of the three-colourability problem.

Finally, a list of three colour labels, one for each graph vertex, is a complexity certificate for the three-colourability problem. Checking all edges takes $O(|V|+|E|)$ time. Hence this problem is in NP as well, and the three-colourability problem is NP-complete.

Let $t_k\in \{0,1\}$ encode the truth value of $X_k$. For a Boolean literal $\ell$, write $L_{\ell }(t)=t_k$ if $\ell =X_k$ and $L_{\ell }(t)=1-t_k$ if $\ell ={\overline{X}}_k$. A clause is true precisely when the sum of its literal values is at least one. Thus the integer programming formulation of satisfiability is the feasibility problemwith objective zero. Every feasible binary vector gives a satisfying assignment of the Boolean satisfiability problem, and conversely. An empty clause gives $0\ge 1$ and hence infeasibility.

For maximum satisfiability, introduce binary variables $q_i$ marking clauses selected as satisfied and solveA false clause forces $q_i=0$, while a true clause permits $q_i=1$. At an optimum every permitted $q_i$ is one, since increasing it improves the objective without affecting another constraint. Therefore the objective is exactly the maximum number of simultaneously true clauses. Repeated literals cause no difficulty, and a clause containing both signs of a variable is always true.

For the literal-frequency greedy approximation for MAX-SAT, keep only clauses not already satisfied and remove literals made false. Count occurrence in clauses, rather than multiplicity within a clause. At a step let $a$ be the number of current clauses containing the chosen literal $z$, and $b$ the number containing its opposite $\overline{z}$. Since $z$ has maximum clause frequency among all remaining literals, $b\le a$.

Setting $z$ true permanently satisfies exactly the $a$ clauses containing it. Some other clauses may become empty and are then permanently lost. Every newly empty clause previously contained $\overline{z}$, so their number $d$ satisfiesA clause containing both signs is satisfied and cannot be one of the lost clauses. Repeat this accounting at every step. Satisfied clauses are removed, so no success is counted twice; each lost nonempty original clause becomes empty at exactly one step. If $G$ is the total number satisfied and $D$ the number of initially nonempty clauses lost, summing the inequalities gives $D\le G$. Every initially nonempty clause eventually falls into one of these two classes. Writing their number as $N_{+}$, we getEven an optimal assignment can satisfy at most $N_{+}$ clauses. ConsequentlyThus Greedy is a $1/2$-approximation in the convention stated in the question. The proof also covers initial empty clauses by excluding them from $N_{+}$; they are unsatisfiable for every algorithm.

The printed interval has a typo: its right endpoint must be $2/3+\delta$, rather than $1/3+\delta$. Keep $\varphi$ as an unnormalized indicator function; only $\psi$ is normalized to have integral one. Thus useWith the Boolean literal printed interval, the convolution vanishes at $2/3$, so a sequence consisting entirely of $2/3$ is already a counterexample to the proposed majorization. For the corrected interval and every $t\in [1/3,2/3]$, all $t-s$ with $|s|\le \delta$ belong to the support of $\varphi$. Hence $f(t)=1$ there. Everywhere $0\le f\le 1$, giving $S_N\le {\sum }_{n\le N}f(u_n)$, including interval endpoints.

Put $L=1/3+2\delta$. For $k\ne 0$, direct integration and the convolution theorem give the exact Fourier coefficientsIn particular,This also supplies the required justification of the Fourier series. The convolution $f$ is continuous: it is the overlap length of two moving intervals, divided by $2\delta$. Its Fourier coefficients are absolutely summable, so the corresponding Fourier series converges uniformly to a continuous function $g$. Termwise integration gives $\hat{g}(k)=\hat{f}(k)$; the permitted uniqueness assertion applied to $f-g$ yields $g=f$.

Let $A_k={\sum }_{n\le N}{e}^{2\pi ik{u}_n}$. Split the absolutely convergent Fourier series at the arbitrary real cutoff $M>1$:There are fewer than $2M$ low-frequency terms and each coefficient has magnitude at most $L<1$. For the tail, $|A_k|\le N$ and ${\sum }_{|k|\ge M}{k}^{-2}\le C/M$. ThereforeThis proves the requested interval discrepancy estimate without an unjustified sharp truncation of the Fourier series.

For a nonzero integer $b$, let $a$ be the nearest integer to $b\sqrt{2}$. The integer $a^2-2b^2$ is nonzero, and $|a|\le \sqrt{2}|b|+1/2$. The suggested factorization yieldsThis is stronger than the stated lower bound for the fractional part, since the distance to the nearest integer is at most that fractional part. For $u_n=n\sqrt{2}$, the geometric series and $|\sin (\pi t)|\ge 2\Vert t{\Vert }_{\mathbb{R}/\mathbb{Z}}$ giveThus the low-frequency contribution is $O(M^2)$. Choose $M=\lceil 100N^{2/5}\rceil$ and $\delta =(2\sqrt{M}{)}^{-1}$; these choices satisfy $0<\delta <1/10$ for every $N\ge 1$. Both $\delta N$ and $N/(\delta M)$ are $O(N^{4/5})$, and so is $M^2$. Hence

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 $M$ 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 $p$ independently leaves each variable live with probability $p$ and otherwise fixes it to zero or one with probability $(1-p)/2$ each. The Håstad switching lemma states that for a width-$w$ DNF or conjunctive normal form $F$,Width bounds Boolean literals in a term or clause, not the number of terms. A decision tree of depth at most $s$ has both a DNF and a conjunctive normal form of width at most $s$ and has real multilinear degree at most $s$. Indeed every leaf condition is a product of at most $s$ factors $x_i$ or $1-x_i$; 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 $1/10$-random restriction. For a bottom AND gate, let $X$ count its live Boolean literals on the event that no fixed Boolean literal kills it. For $w$ distinct Boolean literals,Thus the probability of retaining more than $s$ live Boolean literals without becoming constant is at most $5^{-s}$. 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 $s$, except with probability at most $M_0{5}^{-s}$.

Now apply $d-1$ successive restrictions, each retaining probability $1/(10s)$ of the remaining variables. At a two-layer gate, the current bottom forms are width-$s$ DNFs or conjunctive normal forms. The Håstad switching lemma bounds its probability of failing to reduce to decision-tree depth at most $s$ by $2^{-s}$. Convert the successful decision tree into the opposite normal form, whose terms or clauses have width at most $s$, 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-$s$ decision tree.

The bookkeeping matters: although a decision tree may give $2^s$ 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 $M{2}^{-s}$, 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 probabilityFixed values are still unbiased and coordinates independent. We have proved the useful intermediate estimateFor $d=1$, 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 $J$ be the random live set and $a$ the fixed assignment outside $J$. With ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$, the restricted coefficient at $U\subset J$ isOrthogonality of the fixed-coordinate characters eliminates cross terms after averaging over $a$. Thereforeand then averaging over $J$ gives the expected Fourier weight after a random restriction identityThe 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 $0\le f_{\rho }\le 1$. Hence its expectation is at most $M{2}^{-s}$.

Put $u=t^{1/d}$. If $u\ge 40$, choose $s=\lfloor u/40\rfloor \ge 1$ and the preceding value of $p$. For every $|S|>t$, the binomial distribution mean satisfiesIts variance is at most $\mu$. The Chebyshev inequality givesThus the exact expectation identity bounds at least half the original tail above $t$, andWhen $u<40$ the same bound follows from the trivial total-weight bound ${\sum }_S|\hat{f}(S){|}^2\le 1$. 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 $n$. The original theorem is Linial, Mansour and Nisan's circuit Fourier bound.

Use the specified construction as a polynomial-time many-one reduction from 3-SAT. There are $2n+3m$ vertices and $n+6m$ edges: one edge per variable pair, three edges per clause triangle in a graph, and three occurrence edges per clause. Any vertex cover must take at least one vertex from every variable pair and at least two from every clause triangle. Therefore every cover has at least $n+2m$ vertices.

Given a satisfying Boolean valuation, include the vertex corresponding to the true Boolean literal in each variable pair. In each clause choose a true occurrence and omit its clause vertex, including the other two. Every variable edge and triangle edge is covered. An occurrence edge with an included clause endpoint is covered automatically; the only omitted occurrence vertex is joined to the included true-literal vertex. This is a vertex cover with exactly $n+2m$ vertices.

Conversely, a cover of that size must use exactly one vertex in each variable pair and exactly two in each triangle. Declare a variable true precisely when its positive-literal vertex is included. Each clause has one omitted vertex. Its occurrence edge forces the corresponding literal vertex into the cover, so that literal is true. Every clause is therefore satisfied. ThusThe construction and target size are polynomial in the input length. Since 3-SAT is NP-complete, the decision problem is NP-hard. The usual “at most $k$” version has the same equivalence here because $n+2m$ is an unavoidable lower bound. More generally, a cover with fewer than $k\le |V|$ vertices can be padded to exactly $k$. Verifying a proposed cover is polynomial, so the usual vertex-cover decision problem is also in NP and hence NP-complete.

The three-colourability problem belongs to NP: a colour assignment is a polynomial-length complexity certificate, and all edges can be checked in $O(|V|+|E|)$ time.

For NP-hardness, reduce 3-SAT to the three-colourability problem. Start with a palette graph triangle with vertices $T,F,B$. Its colours are necessarily distinct, and name them by these vertices. For each Boolean variable $u$, add vertices $u,\bar{u}$, join them to each other, and join each to $B$. The graph triangle $B,u,\bar{u}$ is the forcing component of the Boolean-pair colouring gadget, so the two literal vertices receive opposite colours $T,F$.

For each Boolean clause, attach a fresh copy of the three-colour clause gadget, identify its $t$ with the palette vertex $T$, and identify its three input vertices with the Boolean clause's Boolean literal vertices. Copies share only palette or literal vertices. A Boolean clause with one or two Boolean literals is padded to three by repeating a literal; an empty Boolean clause can be mapped immediately to the uncolourable graph $K_4$.

Any graph colouring with three colours gives a truth assignment by reading colour $T$ as true. The three-colour clause gadget forbids three false inputs, so every Boolean clause is satisfied. Conversely, any satisfying truth assignment colours the literal pairs, and the extension property proved above independently colours the fresh auxiliary vertices of each clause. Thus the entire graph is three-colourable exactly when the formula is satisfiable.

There are $3+2n+5m$ vertices for $n$ variables and $m$ nonempty padded clauses, and $O(n+m)$ edges. The construction is a polynomial-time many-one reduction. Using the permitted NP-completeness of 3-SAT, we obtain

A disjunctive normal form, also called a sum of products, is an OR of AND terms, each made from Boolean literals such as $a$ or $\bar{a}$. For example,Here juxtaposition means logical conjunction, $+$ means logical disjunction, and a bar means negation. The expression need not be canonical: a term can omit variables, and need not name a single row of the truth table.

Implement each product by an AND gate and combine the products with an OR gate. Supply complemented inputs with NOT gates. ThusThis is the usual two-level combinational logic realization, counting complemented inputs as available. If NOT gates are counted, a complemented input can traverse three gates. The two-level depth statement also assumes sufficiently large gate fan-in: using only two-input logic gates requires trees for long products or sums. Constant, single-product and single-literal Boolean functions may need fewer levels, so the two-level construction is a general bound, not a claim that every expression requires exactly two layers.

Use two history D flip-flops. Write $a=a_n$, $b=a_{n-1}$ and $c=a_{n-2}$ for the signals just before the active clock edge; update the history by $b^{+}=a$ and $c^{+}=b$. Two or more of the three samples are one exactly when some pair are both one, so the majority function isThree two-input AND gates and one three-input OR gate implement this disjunctive normal form. If a registered output is wanted, feed the expression to the D input of another D flip-flop and capture it at the same edge as the history update. All right-hand sides use the pre-edge values, so no extra sample of delay is introduced.

The three terms are necessary in a minimal sum of products: the input triples $110$, $101$ and $011$ must each be covered, and a single product covering two of them would also cover a triple having only one one. Thus the minimum is three products, each with two Boolean literals.

Keep the two history D flip-flops and add an output D flip-flop with previous value $q=z_{n-1}$. Its next value $q^{+}=z_n$ is one if all three inputs are one, or if the output was one and at least one of the three inputs is one. In the latter case the samples are not all zero, so the previous one must be retained. This givesIf $abc=111$, the first product sets the output. If $abc=000$, every product vanishes and the output clears. For every mixed input triple, at least one of $aq,bq,cq$ equals $q$, so the output is retained. Feed this sum of products to the output D input, use $b^{+}=a,c^{+}=b$ for the history, and use asynchronous clear or an appropriate initialization to establish $q=0$.

Minimality can be seen directly from the truth table. At $q=0$, the only one-entry is $abc=111$, forcing the product $abc$ or a narrower term. At $q=1$, the triples $100$, $010$ and $001$ must all produce one; combining any two in one product would also admit $000$, which must produce zero. Thus three more products are needed. The displayed four products achieve the minimum; removing any Boolean literal from $abc,aq,bq,cq$ would include a zero-entry.

The unconstrained cases can be treated as don't-care conditions during Boolean function minimization. One particularly small, deliberately asymmetric choice isUse the same two history D flip-flops and one output D flip-flop, with this expression at the output D input. It requires two two-input AND gates and one OR gate.

To verify every required case, first set $q=0$. If zero occurs at least twice among $a,b,c$, then $ab=0$, so $q^{+}=0$ as required. If all three samples are one, then $ab=1$, so $q^{+}=1$. The remaining triples have exactly two ones and hence exactly one sample agreeing with the old zero; either output is allowed.

Now set $q=1$. If at least two samples are one, either $c=1$ or $a=b=1$, giving $q^{+}=1$. If all three samples are zero, both terms vanish, giving $q^{+}=0$. The remaining triples have exactly one one and are the allowed don't-care conditions. Thus the expression meets both requirements, including every constant-input triple.

For minimality, consider these required one-entries in $(a,b,c,q)$ order: $1110$, $1101$, $1011$ and $0111$ have no common literal. Therefore a product covering all four would be the constant one, which violates required zero-entries. Also no single-literal product is safe: each of $a,b,c,q$ is one at some required zero-entry, and each complemented literal is one at $0000$. Hence at least two products with at least two Boolean literals each are needed. The displayed expression attains two products and four literals.

Use three D flip-flops whose stored bits $A,B,C$ represent $4A+2B+C$. Initialize them to $000$. The Moore machine's output is this stored binary representation, and its state transition table is:

Treat the two unused state encodings $110,111$ as don't-care conditions when minimizing the sum of products. With juxtaposition for AND, $+$ for OR and a bar for NOT, one minimal choice isFor $D_A$, the required ones at $011$ and $100$ cannot share one valid implicant: their differing bits would force inclusion of required zeros. Pair $011$ with the unused $111$ to get $BC$, and $100$ with unused $110$ to get $A\overline{C}$. Neither term can lose a Boolean literal without covering a required zero.

For $D_B$, state $001$ is isolated from every other required one and from the unused states by required zeros, so it forces the three-Boolean literal term $\overline{A}\overline{B}C$. State $010$ pairs with unused $110$ to give $B\overline{C}$. Finally $D_C=\overline{C}$ is a single Boolean literal. Thus the three expressions are minimal sum of products expressions under the stated unused-state convention. In fact these choices also recover from $110\to 111\to 100$, so initialization into an unused state eventually joins the intended modulo-six counter cycle.

From Boolean clauses containing complementary Boolean literals, derive the Boolean clause formed by removing that complementary pair and taking the remaining Boolean literals. For example, resolving $p\vee \neg q$ with $\neg p\vee \neg r$ gives $\neg q\vee \neg r$. Backward proof search with a positive-headed Horn clause and an all-negative query is a restricted use of this rule.

OR together one minterm for each accepted length-$n$ input. Each minterm is an AND of the appropriate Boolean literals. There are at most $2^n$ minterms, and their negated input wires can be shared, giving $O(n{2}^n)$ bounded-fan-in gates. This is a nonuniform existence statement, not an algorithm for determining an undecidable truth table.

For a CNF input with $n$ Boolean variables, $m$ Boolean clauses, and $L$ Boolean literal occurrences, first check that the supplied Boolean valuation gives each input Boolean variable exactly one truth value. Evaluate each Boolean literal by lookup or logical negation, each Boolean clause by logical disjunction, and the Boolean formula by logical conjunction. Indexed Boolean variables and constant-cost lookups give an $O(n+m+L)$ operation count; with a finite binary string encoding the check still takes polynomial time. Thus a satisfying assignment is a certificate in computational complexity for SAT, proving that SAT belongs to NP. Finding it by exhaustive checking can require $2^n$ candidate Boolean valuations; this enumeration cost is not a lower bound on every possible SAT algorithm.^[ref]