A Polynomial Time Algorithm for 3SAT

Recall an assignment is blocked if it does not allow the clause to evaluate to True.

Since terms in a clause are combined by logical OR operators, a clause cannot evaluate to True if all terms in the clause evaluate to False.

A term evaluates to False if it’s either (1) negated and the terminal’s value is True or (2) positive and the terminal’s value is False.

Given a clause, we know there are some number of unique terminals.

Want to find an assignment where all the terms are assigned a value of False.

Since an assignment exists for all possible values for each terminal, then there exists an assignment such that all the terms in the clause evaluate to False.

Since all the terms evaluate to False and are combined by logical OR operators, the clause will evaluate to False.

Since the instance is composed of clauses combined by logical AND operators and one clause evaluates to False, then the entire instance evaluates to False.

Since the instance evaluates to False, the assignment cannot satisfy the instance. ∎

An assignment for this instance consists of $n$ values, each with two possible values, True or False.

Therefore, there are $2^{n}$ possible assignments. ∎

Consider a clause containing the same terminal in both the positive and negative form.

We know that terminal must either be True or False. Consider both cases:

That terminal’s value is True: The positive form of the terminal will be True and the clause will evaluate to True.

That terminal’s value is False: The negated form of the terminal will be True and the clause will evaluate to True.

Since the clause evaluates to True in every case, there will never be an assignment with which it is impossible to make this clause evaluate to False.

In other words, this clause blocks no assignments. ∎

Consider the generic $k$-terminal clause, $C$, in an instance with $n$ terminals.

As seen in Lemma 5.1, this blocks all assignments where all of the terms evaluate to False.

Since the values for $k$ terminals are set, there are $n-k$ terminals left whose values could be True or False.

Since an assignment exists for every possible way to assign values to each terminal, we know an assignment exists for every possible way to assign a value for these $n-k$ terminals.

There are two possible ways to assign values to each of these $n-k$ terminals so there are $2^{n-k}$ unique assignments blocked by $C$. ∎

We have a clause, $C$, of fixed yet arbitrary length, $k$:

$[a,b,c,...]$

Now we select a terminal, $t$, that’s not in $C$.

Want to show half of the assignments blocked by $C$ assign True to $t$ and the other half assign False to $t$.

We know there will be no overlap between these assignments because a single assignment cannot assign both the values True and False to the same terminal.

Now we just have to show that exactly half of the assignments are blocked by assigning either True or False to $t$.

By Lemma 5.4, $C$ blocks $2^{n-k}$ assignments.

If we fix the value of $t$, then there are only $n-k-1$ terminals whose values could be 0 or 1.

Since there are two choices per terminal and there are $n-k-1$ terminals, then there are $2^{n-k-1}$ assignments blocked by $C$ where the value of $t$ is fixed.

Divide to get the ratio of the number of assignments blocked by adding $t$ to the number of assignments blocked by $C$ without $t$:

$2^{n-k-1}/2^{n-k}$

= $2^{n-k-1-(n-k)}$

= $2^{-1}$

= $1/2$

This shows that half of the assignments blocked by $C$ assign a fixed value to $t$.

Since there are two possible values for $t$ and each block mutually exclusive halves of the assignments blocked by $C$, the lemma holds. ∎

Given a clause, $C$, of a fixed yet arbitrary length:

$C:=[a,b,c,...]$

And another clause, $D$, containing all the terms in $C$ with possibly additional terms:

$D:=[a,b,c,...,d,e,f,...]$

Want to show all the assignments blocked by $D$ are also blocked by $C$.

We know that $C$ blocks all assignments that cause all the terms to evaluate to False.

In other words, $C$ blocks all assignments where

$a=b=c=...=False$

Similarly, $D$ blocks all assignments where

$a=b=c=...=d=e=f=...=False$

Clearly all assignments consistent with the terminal assignments from $D$ are also consistent with the terminal assignments from $C$.

Therefore, every assignment blocked by $D$ is also blocked by $C$. ∎

Given clauses consistent with the description:

$A:=[a,b,c,...i]$

$B:=[a,b,c,...,-i]$

where $a,b,c,...$ is shared between the clauses and $i$ is a terminal not in $a,b,c,...$

Want to show this implies $C$.

Recall by Lemma 5.3 that the same terminal cannot appear both negated and positive within the same clause and still block an assignment, so $i$ cannot exist in $a,b,c...$

Consider the clause

$C:=[a,b,c,...]$

We know by Lemma 5.5 that if we select a terminal that’s not in $C$, say $t$, then half of the assignments blocked by $C$ assign True to $t$ and the other half of the assignments blocked by $C$ assign False to $t$.

Let this terminal $t$ that’s not in $C$ be the terminal $i$ that’s in $A$ and $B$.

We know that $A$ blocks all assignments blocked by $C$ where $i$ is assigned the value of False.

We know that $B$ blocks all assignments blocked by $C$ where $i$ is assigned the value of True.

Since $A$ and $B$ both block mutually exclusive halves of the assignments blocked by $C$, then all of the assignments blocked by $C$ are blocked by $A$ and/or $B$ and we can say that $A$ and $B$ imply $C$. ∎

Given a clause, $C$, and a terminal, $t$, that’s not in $C$:

$C:=[a,b,c,...]$

We can compose two new clauses:

$D:=[a,b,c,...,t]$

$E:=[a,b,c,...,-t]$

Since all of the terms in $C$ exist in $D$ and $E$, then by Lemma 5.6 all of the assignments blocked by $D$ or $E$ are blocked by $C$ and we can say $D$ and $E$ are implied by $C$. ∎

Consider two clauses,

$C:=[a,b,c,...,t]$

$D:=[d,e,f,...,-t]$

Where within a clause, the same terminal does not repeat, but between clauses the same terminal may repeat.

Want to show we can imply a clause consistent with the lemma description:

$E:=[a,b,c,...,d,e,f,...]$

Let’s define some additional clauses:

$E^{\prime}:=[a,b,c,...,d,e,f,...,t]$

$E^{\prime\prime}:=[a,b,c,...,d,e,f,...,-t]$

By Lemma 5.6, we know that $C$ implies $E^{\prime}$ because all the terms in $C$ exist in $E$.

By Lemma 5.6, we know that $D$ implies $E^{\prime\prime}$.

By Lemma 5.7, since $E^{\prime}$ and $E^{\prime\prime}$ share all the same terms except for $t$, which is positive in one clause and negated in the other, we can create a new clause composed of all the shared terms in $E^{\prime}$ and $E^{\prime\prime}$.

Such a clause is already defined as $E$.

Now there are a couple extra cases to consider:

• •

  There is some overlap between $a,b,c,...$ and $d,e,f,...$

• •

  There is the same terminal that’s positive in $a,b,c,...$ and negated in $d,e,f,...$

First, if the same term exists in $a,b,c,...$ and $d,e,f,...$, then we can just remove one of the duplicates since one term being True implies an identical term being True.

Secondly, if the same terminal exists, but is of the opposite form in $a,b,c,...$ and $d,e,f,...$ then by Lemma 5.3, this clause will always be True and thus blocks no assignments. In this case, the lemma is vacuously true, but we disregard the clause as it is of no value. ∎

The smallest clause that can be implied by clauses of length $k$ and $m$ using Lemma 5.9 occur when all but one of the terms in one clause exist in the other.

As such, the unique terms will come from the clause that’s longer.

Removing $t$, you are left with 1 less than the maximum of $k$ and $m$.

The largest clause can be implied if there are no terms shared between the two clauses. In this case you subtract $1$ from the length of each clause to account for $t$ and since no duplicates will be removed, the resulting clause’s length is $2$ less than the sum of the lengths of the clauses. ∎

Define the clauses in the following manner:

A := [a, b, $\beta$, i]

B := [c, d, $\delta$ -i]

C := [-a, e, f, $\phi$]

Then the following are derived by Lemma 5.9:

$E=[a,b,\beta,c,d,\delta]$ (By $A$ and $B$)

$D=[b,\beta,c,d,\delta,e,f,\phi]$ (By $C$ and $E$ or by $F$ and $B$)

$F=[b,\beta,i,e,f,\phi]$ (By $A$ and $C$)

Where $\beta,\delta,$ and $\phi$ are generic sets of terms in the instance.

Consider the following figure:

Note that since $C$ and $E$ imply $D$, then $C$ and $E$ must share the same terminal such that it is positive in one clause and negated in the other.

Since all of the terms in $E$ came from $A$ or $B$ (not including $i$), then such a term in $C$ must have the same term of the opposite form in $A$ or $B$.

And since $A$ and $B$ are fixed yet arbitrary clauses treated in the same way, it does not matter which clause we pick as long as it is fixed for the rest of the proof. Let’s pick a the terminal, $a$, from clause $A$. Now $C$ contains $-a$.

Recall from Lemma 5.3 that if a clause blocks any assignments, it cannot contain the same term in both forms, so if $\beta,\delta$, or $\phi$ contain the same terminal in both forms then $D$ blocks no assignments and the resulting clause may be disregarded.

We know $C$ is of length $k$ and there are two cases for $D$: (1) $D$ is of length $k$ or (2) $D$ is of length $k-1$.

In the following equations, let the presence of a term represent a count of one, and the presence of a set of terms represent the number of terms in that set. If multiple sets of terms are shown in parentheses, let this represent the number of terms found in the intersection of both sets.

Consider (1) the case where $D$ has length $k$ then we can define $k$ in terms of $D$:

$k=b+c+d+e+f+\beta+\delta+\phi-(\beta\delta)-(\beta\phi)-(\delta\phi)+(\beta\delta\phi)$

length of $F=b+i+e+f+\beta+\phi-(\beta\phi)$

Want to show length of $F$ is less than $k$

$b+i+e+f+\beta+\phi-(\beta\phi)<b+c+d+e+f+\beta+\delta+\phi-(\beta\delta)-(\beta\phi)-(\delta\phi)+(\beta\delta\phi)$

$\rightarrow$ $i+\beta+\phi-(\beta\phi)<c+d+\beta+\delta+\phi-(\beta\delta)-(\beta\phi)-(\delta\phi)+(\beta\delta\phi)$

$\rightarrow$ $i<c+d+\delta-(\beta\delta)-(\delta\phi)+(\beta\delta\phi)$

As seen by using a Venn Diagram or other set intuition, $\delta-(\beta\delta)-(\delta\phi)+(\beta\delta\phi)$, represents the number of terminals in $\delta$ not in $\beta$ and not in $\phi$.

The lowest case for the right hand side of the inequality is where this is 0, ie, all of the terms in $\delta$ are in $\beta$ or $\phi$. In this case, the inequality becomes:

$\rightarrow$ $i<c+d$

Which is true as long as $c$ and $d$ exist in $B$.

Want to show $c$ and $d$ always exists in $B$:

Suppose not, then at most one of $c$ or $d$ exists.

Recall we have the clauses:

$A:=[a,b,\beta,i]$

$B:=[c,d,\delta,-i]$

$E:=[a,b,\beta,c,d,\delta]$

And since only $c$ or $d$ exist, we can redefine some clauses:

$B:=[x,-i]$

$E:=[a,b,\beta,x]$

Where x is represents either $c$ or $d$, but not both.

Note that no terms may exist in $\delta$ because any terms in $\delta$ could be extracted and treated as $c$ or $d$, but we know $x$ already represents the one of these terms that exist and the other term cannot exist.

Notice the length of $A$ is the same as the length of $E$.

This is a contradiction because the length of $A$ is given as less than $k$ and the length of $E$ is given as $k$.

Therefore both $c$ and $d$ must exist and the inequality is true.

Therefore $F$ is shorter than $k$ when $D$ is of length $k$.

Consider (2) the case where the length of $D$ is $k-1$:

This means $k$ is one greater than the length of $D$, so $k$ is now:

$k=b+c+d+e+f+\beta+\delta+\phi-(\beta\delta)-(\beta\phi)-(\delta\phi)+(\beta\delta\phi)+1$

length of $F=b+i+e+f+\beta+\phi-(\beta\phi)$

Want to show length of $F$ is less than $k$

$b+i+e+f+\beta+\phi-(\beta\phi)<b+c+d+e+f+\beta+\delta+\phi-(\beta\delta)-(\beta\phi)-(\delta\phi)+(\beta\delta\phi)+1$

Similarly as before, the inequality will become:

$\rightarrow$ $i<c+d+1$

Which is true as long as at least $c$ or $d$ exist.

It was seen that both $c$ and $d$ must exist and since the proof does not rely on the length of $D$, the inequality is true.

Therefore the length of $F$ is shorter than $k$ when the length of $D$ is $k-1$.

Since the length of $F$ is less than $k$ in all cases, you can derive $D$ by processing only clauses with a maximum length of $k-1$. ∎

Let the clauses be defined as follows:

$A:=[a,b,\beta]$

$B:=[a,b,\beta,c,d,\delta]$

$C_{1}$ := [-a, e, f, $\phi$]

$C_{2}$ := [-c, e, f, $\phi$]

$D_{1}$ := [b, $\beta$, c, d, $\delta$, e, f, $\phi$]

$D_{2}$ := [a, b, $\beta$, d, $\delta$, e, f, $\phi$]

E := [b, $\beta$, e, f, $\phi$]

Where $\beta,\delta$, and $\phi$ are fixed, yet arbitrary sets of terms such that the clauses block at least one assignment.

Consider the following figure

Notice that $C$ has to contain a term from $B$ in the opposite form by Lemma 5.9.

Notice that $B$ is made up of terms from $A$ and terms not in $A$ by Lemma 5.6.

The term in $C$ which is opposite from the term in $B$ can therefore be opposite (1) from a term in $A$ (in this case, use $C_{1}$ and $D_{1}$) or (2) a term not in $A$ (in this case use $C_{2}$ and $D_{2}$).

(1) Consider the opposite form term in $C$ is in $A$ (use $C_{1}$ and $D_{1}$):

Recall the clauses:

$A:=[a,b,\beta]$

$C_{1}$ := [-a, e, f, $\phi$]

$D_{1}$ := [b, $\beta$, c, d, $\delta$, e, f, $\phi$]

$E:=[b,\beta,e,f,\phi]$

Notice $A$ and $C_{1}$ share an opposite term, so they can derive a clause, $E$, by Lemma 5.9.

Notice all the terms in $E$ exist in $D_{1}$ so $E$ can be expanded to derive $D_{1}$ by Lemma 5.8.

Consider the path of implication in the following figure:

Want to show you only have to process clauses whose length is less than $k$ to derive $D_{1}$.

Since $D_{1}$ is derived using only $A$, $C_{1}$, and $E$ and $A$ and $C$ are given to be shorter than $k$, want to show length of $E$ is less than $k$.

Consider two cases: (1a) $D_{1}$ is of length $k$ and (1b) $D_{1}$ is of length $k-1$

Consider (1a) where $D_{1}$ is of length $k$:

In the following equations, let the presence of a term represent a count of one, and the presence of a set of terms represent the number of terms in that set. If multiple sets of terms are shown in parentheses, let this represent the number of terms found in the intersection of both sets.

Since $D_{1}$ is of length $k$, we can define $k$ as follows:

$k=b+c+d+e+f+\beta+\delta+\phi-(\beta\delta)-(\beta\phi)-(\delta\phi)+(\beta\delta\phi)$

Length of $E=b+e+f+\beta+\phi-(\beta\phi)$

Want to show the length of $E$ is less than $k$:

$b+e+f+\beta+\phi-(\beta\phi)<b+c+d+e+f+\beta+\delta+\phi-(\beta\delta)-(\beta\phi)-(\delta\phi)+(\beta\delta\phi)$

$\rightarrow 0<c+d+\delta-(\beta\delta)-(\delta\phi)+(\beta\delta\phi)$

Which is true as long as at least one term exists on the R.H.S.

Want to show at least one term exists on the R.H.S.

Suppose not, then no terms exist on the R.H.S. and we can redefine some clauses.

Recall the original clause definitions:

$A:=[a,b,\beta]$

$B:=[a,b,\beta,c,d,\delta]$

Since no terms exist on the R.H.S. we can redefine some clauses:

$B:=[a,b,\beta]$

Note that no terms may exist in $\delta$ because any term in $\delta$ can be extracted and treated as $c$ or $d$ and those are explicitly removed from existence.

Notice $A$ is exactly $B$.

This is a contradiction because the length of $A$ is given as less than $k$ while the length of $B$ is given as $k$.

Therefore at least one term must exist on the R.H.S. and the inequality holds.

Therefore $E$ is shorter than $k$ when $D$ is of length $k$ and we use $C_{1}$ and $D_{1}$.

Consider (1b) $D_{1}$ is of length $k-1$:

Then the length of $k$ is redefined as:

$k=b+c+d+e+f+\beta+\delta+\phi-(\beta\delta)-(\beta\phi)-(\delta\phi)+(\beta\delta\phi)+1$

Similarly as before, the inequality becomes:

$\rightarrow 0<c+d+1$

Which is always true so the length of $E$ is indeed less than $k$ when $D$ is of length $k-1$ and we use $C_{1}$ and $D_{1}$.

(2) Consider the case using $C_{2}$ and $D_{2}$:

Recall the clauses:

$A:=[a,b,\beta]$

$C_{2}=[-c,e,f,\phi]$

$D_{2}=[a,b,\beta,d,\delta,e,f,\phi]$

Since all of the terms in $A$ exist in $D_{2}$, we can expand $A$ to $D_{2}$ using Lemma 5.8

Since the length of $A$ is given as less than $k$, we can derive $D$ by processing clauses with a maximum length of $k-1$.

Since the possible lengths of $D$ are $k$ or $k-1$ and in both cases we derive $D$ by processing clauses with a maximum length of $k-1$ then $D$ can always be derived by processing clauses with a maximum length of $k-1$. ∎

Given an instance of 3SAT, we know all clauses are of length 3.

If we want to consider a generic $n$-terminal clause, $B$, that’s implied by a given clause, $A$, then by Lemma 5.6 we know it’s implied if all the terms in $A$ exist in $B$. ∎

Want to show an unsatisfiable instance $\implies$ $2^{n}$ unique n-terminal clauses can be derived from the given 3-t clauses:

By lemma 5.4, a clause of length $n$ blocks 1 assignment.

Recall an instance is unsatisfiable iff all $2^{n}$ assignments are blocked.

If a 3-terminal clause blocks an assignment, then it also implies the corresponding n-terminal assignment because there is one possible n-terminal clause for any given assignment.

Notice that for each of these n-terminal clauses, they must contain three terms from at least one given clause. If they didn’t, then the assignment blocked by that n-terminal clause would not be blocked and the instance would be satisfiable.

Since each n-terminal clause blocks one assignment, blocking all assignments requires $2^{n}$ n-terminal clauses.

Want to show $2^{n}$ unique n-terminal clauses are derived by the given 3-t clauses $\implies$ then the instance is unsatisfiable.

By lemma 5.4, a clause of length $n$ blocks 1 assignment.

Therefore if there are $2^{n}$ unique n-terminal clauses, then all $2^{n}$ assignments will be blocked.

Note that there will be no overlap because each n-terminal clause sets the value for each terminal and overlap would imply the same terminal having two values by the same assignment which is impossible. ∎

Given $2^{n}$ n-terminal clauses, want to show you can imply any pair of contradicting 1-terminal clauses by lemma 5.7.

Algorithm:

Pick a terminal that will not exist in the final 1-terminal clauses.

Notice half of the existing n-terminal clauses have that terminal assigned the value of False and the other half have that terminal assigned the value of True.

Pick one clause that blocks an assignment where the terminal is True.

Then there exists an assignment for each possible value for the remaining n-1 terminals.

Therefore, there must exist another clause that shares all of the same terms, but where that one terminal is assigned the value of False.

Using these two clauses, we can create a new clause by lemma 5.7.

Now all of the clauses of length n - 1 do not contain that terminal.

Repeat this process while never selecting the same terminal twice until you are left with two contradicting 1-terminal clauses.

Each clause is guaranteed to have a matching clause since every possible combination of terminal assignments exists and when you use Lemma 5.7 to create new clauses, the rest of all of the clauses remain the same except the selected terminal is removed. ∎

Let the following clauses be a pair of contradicting 1-t clauses:

$[a]$

$[-a]$

Any possible clause could either contain $a$, $-a$, or neither.

By lemma 5.8, we can expand to any clause that contains $a$ or $-a$.

Now want to show these clauses imply another clause that does not contain $a$ or $-a$.

Let the following be a generic k-terminal clause that does not contain $a$ or $-a$:

$[b,c,d,...]$

By Lemma 5.8, we know the 1-terminal clauses imply the following clauses:

$[a,b]$

$[-a,c,d,...]$

By Lemma 5.9, these clauses imply:

$[b,c,d,...]$

Therefore a set of contradicting 1-terminal clauses can imply any clause containing $a,-a$, or neither, which encompasses every possible clause. ∎

Consider the following figure:

Let the clauses be defined as follows:

$A:=[a,b,\beta,i]$

$B:=[c,d,\delta,-i]$

$C:=[-a,f,\phi,j]$

$D:=[g,h,\gamma,-j]$

Then the following are implied by Lemma 5.9:

$E=[a,b,\beta,c,d,\delta]$

$F=[-a,f,\phi,g,h,\gamma]$

$G=[b,\beta,c,d,\delta,f,\phi,g,h,\gamma]$

Where $\beta,\delta,\phi,$ and $\gamma$ are fixed yet arbitrary sets of terms such that the clauses block at least one assignment.

Notice that $E$ and $F$ have to share a term of the opposite form in order to imply $G$ by Lemma 5.9.

All of the terms in $E$ and $F$ came from $A,B,C,$ and $D$.

Since $A,B,C,$ and $D$ are all arbitrary clauses, selecting which term to negate does not have an effect on the outcome as long as one form of the term exists in $E$ and the other form exists in $F$.

Here the opposite term is shared between $A$ and $D$, but any term that appears positive in $A$ or $B$ and negated in $C$ or $D$ or vice versa will yield the same results.

Want to show $G$ can be derived by processing clauses with a maximum length of $k-1$.

Define additional implications by Lemma 5.9:

$H=[b,\beta,i,f,\phi,j]$ (By clauses $A$ and $C$)

$I=[c,d,\delta,b,\beta,f,\phi,j]$ (By clauses $B$ and $H$)

$J=[g,h,\gamma,c,d,\delta,b,\beta,f,\phi]$ (By clauses $D$ and $I$)

Notice $J$ is equivalent to $G$.

Want to show all clauses used to derive $J$ are shorter than $k$.

Want to show $A$, $C$, $B$, $H$, $D$, and $I$ are shorter than $k$.

It was given that $A$, $B$, $C$, and $D$ are shorter than $k$ so just want to show $H$ and $I$ are shorter than $k$.