-
Notifications
You must be signed in to change notification settings - Fork 1
/
polytime.tex
1942 lines (1294 loc) · 80.8 KB
/
polytime.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[manuscript]{acmart}
\usepackage{graphicx}
\graphicspath{{./Source/}}
\begin{document}
\title{A Polynomial Time Algorithm for 3SAT}
\author{Robert Quigley}
\email{[email protected]}
\begin{abstract}
It is shown that any two clauses in an instance of 3SAT sharing the same terminal which is positive in one clause and negated in the other can imply a new clause composed of the remaining terms from both clauses. Clauses can also imply other clauses as long as all the terms in the implying clauses exist in the implied clause. It is shown an instance of 3SAT is unsatisfiable if and only if it can derive contradicting 1-terminal clauses in exponential time. It is further shown that these contradicting clauses can be implied with the aforementioned techniques without processing clauses of length 4 or greater, reducing the computation to polynomial time. Therefore there is a polynomial time algorithm that will produce contradicting 1-terminal clauses if and only if the instance of 3SAT is unsatisfiable. Since such an algorithm exists and 3SAT is NP-Complete, we can conclude P = NP.
\end{abstract}
\keywords{NP-Complete, SAT, 3SAT, Satisfiability, P vs NP, Polynomial Time, Non-deterministic Polynomial Time, Complexity Theory, Computational Complexity, Complexity Classes, Cook-Levin Theorem, Karp's 21 NP-Complete Problems}
\begin{CCSXML}
<ccs2012>
<concept>
<concept_id>10003752.10003777.10003778</concept_id>
<concept_desc>Theory of computation~Complexity classes</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>
\end{CCSXML}
\ccsdesc[500]{Theory of computation~Complexity classes}
\maketitle
\section{Introduction}
This section introduces the 3SAT problem, the implications of
solving it in polynomial time, and the structure of the paper.
As seen in \cite{10.1145/800157.805047},
The boolean satisfiability problem is given as a set of terminals, $x_1, x_2, ..., x_n$,
each of which can be assigned a value of True or False,
combined by logical AND operators, logical OR operators, and negations.
The problem is to determine whether or not there exists an assignment
for each terminal that allows the instance to evaluate to True.
As seen in \cite{Karp1972}, the satisfiability problem
with exactly 3 literals per clause is NP-Complete. This is the same
as the boolean satisfiability problem, but it is presented such that
a clause contains exactly three terminals combined with logical OR operators
and possibly negations, and each clause is combined with logical AND operators.
The idea of NP-completeness shows that if one NP-complete problem can be solved
in polynomial time, then all problems in the class NP can be solved in polynomial time.
In other words, P = NP.
The paper is structured as follows:
\begin{enumerate}
\item Introduction
\item Standard Definitions
\begin{itemize}
\item Terms relating to the 3SAT problem
\end{itemize}
\item Algorithm-Specific Definitions
\begin{itemize}
\item Terms relating to specific aspects of 3SAT regularly referenced in this paper
\end{itemize}
\item Reformatting and Processing
\begin{itemize}
\item Defines how clauses and instances of the 3SAT problem will appear within the paper
\end{itemize}
\item Lemmas
\begin{itemize}
\item A list of lemmas and their proofs pertaining to the algorithm
\end{itemize}
\item Algorithm
\begin{itemize}
\item A step-by-step description of the algorithm to solve 3SAT in polynomial time
\end{itemize}
\item Time Complexity Analysis
\begin{itemize}
\item An analysis of the time complexity of the algorithm
\end{itemize}
\item Proof of Correctness
\begin{itemize}
\item A proof showing the algorithm works for every instance of 3SAT
\end{itemize}
\item Conclusion
\item References
\end{enumerate}
\section{Standard Definitions}
\begin{definition}
Terminals: symbols used in the 3SAT problem that can be assigned a value
of either 0 or 1, True or False, or any other binary assignment. They usually
take the form $x_i$ where $i$ is a natural number.
\end{definition}
\begin{definition}
Terms: terminals in either the positive or negated form that appear in a clause.
If a term is positive, then the value of the terminal will be the
same as the value of the term. If a term is negated, then the value
of the terminal will be the opposite of the value of the term.
\end{definition}
\begin{definition}
Clauses: a set of terms combined by logical OR operators.
Clauses usually take the form
$(x_i \lor \neg x_j \lor x_k)$ where $x_i \neq x_j \neq x_k$.
\end{definition}
\begin{definition}
(3SAT) Instance: a set of any number of clauses combined by logical
AND operators. Terminals may not repeat within a clause
\footnote{See Lemma 5.3}
, but they are free to repeat between clauses.
Instances usually take the form:
$(x_i \lor \neg x_j \lor x_k) \land (x_l \lor x_m \lor x_n)$.
\end{definition}
\begin{definition}
Assignment: A list of values in which each value represents either True
or False such that each item in the list corresponds to a terminal and
all terminals are assigned a value.
\end{definition}
\begin{definition}
Satisfying Assignment: An assignment, $A$, is said to satisfy the instance if applying $A$ will make the instance evaluate to True.
\end{definition}
\begin{definition}
Satisfiable: an instance is satisfiable iff there exists a satisfying assignment.
\end{definition}
\begin{definition}
Unsatisfiable: an instance is unsatisfiable iff there does not exist a satisfying assignment.
\end{definition}
\section{Algorithm-Specific Definitions}
\begin{definition}
Blocking an Assignment: An assignment, $A$, is said to be blocked by a clause, $C$ if,
given an instance containing $C$, there is no way that $A$ allows $C$ to evaluate to True, and
thus there is no way $A$ allows the instance to evaluate to True.
\end{definition}
\begin{definition}
Implication: A clause, $C$, is said to imply another clause, $D$, if all
assignments blocked by $D$ are also blocked by $C$.
\end{definition}
\begin{definition}
Given Clauses: clauses which were given in the original instance.
\end{definition}
\begin{definition}
Derived or Implied Clauses: clauses which are implied by the clauses in the original instance.
\end{definition}
\begin{definition}
k-terminal (k-t) clause: a clause is described as a k-terminal or a k-t clause
if there are $k$ terminals in the clause.
\end{definition}
\begin{definition}
Reduction: A special type of implication in which the implied
clause is shorter than the implying clause(s).
\end{definition}
\begin{definition}
Expansion: A special type of implication in which the
implied clause is longer than the implying clause(s) and all terms in the implying
clause exist in the implied clause.
\end{definition}
\begin{definition}
Contradicting 1-terminal Clauses: A set of two clauses are considered to be contradicting 1-terminal clauses if (1) they are both of length 1, (2) they contain the same terminal, and (3) the terminal is positive in one clause and negated in the other.
\end{definition}
\section{Reformatting and Processing}
Since there are a lot of constant characteristics about an instance of 3SAT,
we can remove most of them to allow ourselves to focus only on what changes
from instance to instance. A list of unchanging characteristics follows:
\begin{itemize}
\item the symbol $x$
\item logical AND operators
\item logical OR operators
\end{itemize}
The only difference between instances, therefore, is the subscript of the terminal.
Additionally, the following items will be changed to improve compatibility
with the Python programming language wherein an instance is expressed as
a list of lists and each inner list represents a clause:
\begin{itemize}
\item parentheses will become square brackets
\item negation symbols will become minus signs
\item an instance may be surrounded with square brackets to show it is a list of lists
\end{itemize}
For example, the instance:
$(\neg x_a \lor x_b \lor x_c) \land (x_a \lor x_d \lor x_e)$
will be written as:
$[[-a, b, c], [a, d, e]]$
Instances of 3SAT will further be processed by removing any clauses that do not block
any assignments. Since this algorithm relies on implications of new clauses, if we ever
come across a clause that blocks no assignments, then by definition it will not be able
to imply any additional clauses that block at least one assignment.
As such, we will ignore any clauses given or derived that are described in Lemma 5.3
\section{Lemmas}
\begin{lemma}
A clause can block an assignment.
\end{lemma}
\begin{proof}
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.
\end{proof}
\begin{lemma}
For a given instance with $n$ terminals, there are $2^n$ possible assignments.
\end{lemma}
\begin{proof}
An assignment for this instance consists of $n$ values, each with two possible values, True or False.
Therefore, there are $2^n$ possible assignments.
\end{proof}
\begin{lemma}
If a clause contains the same terminal in its negated and positive form, it will not block any assignments.
\end{lemma}
\begin{proof}
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.
\end{proof}
\begin{lemma}
Each clause of length $k$ blocks $2^{n-k}$ assignments.
\end{lemma}
\begin{proof}
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$.
\end{proof}
\begin{lemma}
For any clause, $C$, if we select a terminal, $t$, that's not in $C$ then half of the assignments blocked by $C$ will assign True to $t$ and the other half will assign
False to $t$.
\end{lemma}
\begin{proof}
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.
\end{proof}
\begin{lemma}
Given a clause, $C$, and another clause, $D$, such that all of the terms in $C$ also exist in $D$, then all of the assignments blocked by $D$ are also blocked by $C$.
\end{lemma}
\begin{proof}
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$.
\end{proof}
\begin{lemma}[Reduction]
Given the following conditions:
\begin{itemize}
\item $A$ is a clause of length $k$
\item $B$ is a clause of length $k$
\item $A$ and $B$ share $k-1$ identical terms
\item $A$ and $B$ share one terminal that is negated in one clause
and positive in the other
\item $C$ is a clause of length $k-1$ composed of the shared terms
from $A$ and $B$
\end{itemize}
Then $A$ and $B$ imply $C$.
\end{lemma}
\begin{proof}
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$.
\end{proof}
\begin{lemma}[Expansion]
Given a clause, $C$, and a terminal, $t$, that's not in $C$, then two new clauses can be implied consisting of all the terms of $C$ appended to either the positive form of $t$ or the negated form of $t$.
\end{lemma}
\begin{proof}
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$.
\end{proof}
\begin{lemma}[General Lemma 5.7]
If two clauses share the same terminal, $t$, such that $t$ is positive in one clause and negated in the other, then these clauses imply a new clause which is composed of all the terms in both clauses except terms containing $t$.
\end{lemma}
\begin{proof}
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' := [a, b, c, ..., d, e, f, ..., t]$
$E'' := [a, b, c, ..., d, e, f, ..., -t]$
By Lemma 5.6, we know that $C$ implies $E'$ because all the terms in $C$ exist in $E$.
By Lemma 5.6, we know that $D$ implies $E''$.
By Lemma 5.7, since $E'$ and $E''$ 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'$ and $E''$.
Such a clause is already defined as $E$.
Now there are a couple extra cases to consider:
\begin{itemize}
\item There is some overlap between $a, b, c, ...$ and $d, e, f, ...$
\item There is the same terminal that's positive in $a, b, c, ...$ and negated in $d, e, f, ...$
\end{itemize}
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.
\end{proof}
\begin{lemma}
Given two clauses of lengths $k$ and $m$ that imply another clause by Lemma 5.9, the length of the implied clause will fall in the range $max(k, m)-1$ to $(k + m - 2)$ where the $max(k, m)$ represents the parameter with the greatest value.
\end{lemma}
\begin{proof}
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.
\end{proof}
\begin{lemma}
Given the following:
\begin{itemize}
\item A clause, $A$, of length less than $k$
\item A clause, $B$, of length less than $k$
\item A clause, $C$, of length less than $k$
\item A clause, $D$, of length $k$ or $k - 1$
\item A clause, $E$, of length $k$
\item $A$ and $B$ imply $E$ by Lemma 5.9
\item $C$ and $E$ imply $D$ by Lemma 5.9
\end{itemize}
Then $A$, $B$, and $C$, imply $D$ by processing only clauses with a maximum length of $k - 1$.
\end{lemma}
\begin{proof}
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:
\begin{figure}[H]
\includegraphics[scale=0.8]{511a}
\caption{A graph illustrating the derivations described by the lemma}
\Description[A graph illustrating the derivations described by the lemma]{A graph illustrating the derivations described by the lemma}
\end{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$.
\end{proof}
\begin{lemma}
Given the following:
\begin{itemize}
\item $A$ is a clause of length less than $k$
\item $B$ is a clause of length $k$
\item $C$ is a clause of length less than $k$
\item $D$ is a clause of length $k$ or $k - 1$
\item $A$ expands to imply $B$ by Lemma 5.8
\item $B$ and $C$ imply $D$ by Lemma 5.9
\end{itemize}
Then $D$ can be implied by processing clauses of at most length $k - 1$.
\end{lemma}
\begin{proof}
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
\begin{figure}[h]
\includegraphics[scale=0.8]{318}
\caption{An illustration of the derivations described in the lemma}
\Description[An illustration of the derivations described in the lemma]{An illustration of the derivations described in the lemma}
\end{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:
\begin{figure}[h]
\includegraphics[scale=0.8]{318b.png}
\caption{An illustration of the derivations by clauses $A$, $C_1$, and $E$}
\Description[An illustration of the derivations by clauses $A$, $C_1$, and $E$]{An illustration of the derivations by clauses $A$, $C_1$, and $E$}
\end{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$.
\end{proof}
\begin{lemma}
Given an instance of 3SAT, you can expand all of the given clauses to the point where you are considering clauses of length $n$.
\end{lemma}
\begin{proof}
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$.
\end{proof}
\begin{lemma}
If you expand given 3-t clauses as described in Lemma 5.13, you will
derive $2^n$ unique clauses of length $n$ iff the instance is unsatisfiable.
\end{lemma}
\begin{proof}
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.
\end{proof}
\begin{lemma}
The n-terminal clauses described in Lemma 5.14 can be reduced to derive any pair of contradicting 1-terminal clauses.
\end{lemma}
\begin{proof}
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.
\end{proof}
\begin{lemma}
Contradicting 1-terminal clauses can be expanded to imply every possible clause.
\end{lemma}
\begin{proof}
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.
\end{proof}
\begin{lemma}
Given the following:
\begin{itemize}
\item A, B, C, and D, are clauses shorter than k
\item E and F are clauses of length k
\item G is a clause of length k or k - 1
\item A and B imply E by Lemma 5.9
\item C and D imply F by Lemma 5.9
\item E and F imply G by Lemma 5.9
\end{itemize}
Then G can be implied by processing clauses with a maximum length of k - 1.
\end{lemma}
\begin{proof}
Consider the following figure:
\begin{figure}[h]
\includegraphics[scale=0.8]{517a.png}
\caption{An illustration of the derivations described in the lemma}
\Description[An illustration of the derivations described in the lemma]{An illustration of the derivations described in the lemma}
\end{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$.
Want to show (1) $H$ is shorter than $k$ and (2) $I$ is shorter than $k$
(1) Want to show $H$ is shorter than $k$
Two cases to consider (1a) $G$ is of length $k$ and (1b) $G$ is of length $k - 1$
(1a) $G$ 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 $G$ is of length $k$ we can define $k$ as follows:
$k = b + c + d + f + g + h
+ \beta + \delta + \phi + \gamma
- (\beta \delta) - (\beta \phi) - (\beta \gamma) - (\delta \phi) - (\delta \gamma) -(\phi \gamma)
+ (\beta \delta \phi) + (\beta \delta \gamma) + (\beta \phi \gamma) + (\delta \phi \gamma)
- (\beta \delta \phi \gamma)
$
Length of $H = b + i + f + j + \beta + \phi - (\beta \phi)$
Want to show the length of $H$ is less than $k$:
$b + i + f + j + \beta + \phi - (\beta \phi)$
$<$
$b + c + d + f + g + h
+ \beta + \delta + \phi + \gamma
- (\beta \delta) - (\beta \phi) - (\beta \gamma) - (\delta \phi) - (\delta \gamma) -(\phi \gamma)
+ (\beta \delta \phi) + (\beta \delta \gamma) + (\beta \phi \gamma) + (\delta \phi \gamma)
- (\beta \delta \phi \gamma)
$
$\rightarrow$
$i + j$
$<$
$c + d + g + h
+ \delta + \gamma
- (\beta \delta) - (\beta \gamma) - (\delta \phi) - (\delta \gamma) -(\phi \gamma)
+ (\beta \delta \phi) + (\beta \delta \gamma) + (\beta \phi \gamma) + (\delta \phi \gamma)
- (\beta \delta \phi \gamma)
$
Which is true as long as at least three terms exist on the R.H.S.
Consider the following cases:
\begin{itemize}
\item No terms exist on the R.H.S.
\item Exactly one term exists on the R.H.S.
\item Exactly two terms exist on the R.H.S.
\end{itemize}
Consider case 1 where no terms exist on the R.H.S.
Recall the clauses:
$A := [a, b, \beta, i]$
$B := [c, d, \delta, -i]$
$E := [a, b, \beta, c, d, \delta]$
But since no terms exist on the R.H.S., specifically $c$ and $d$ don't exist, we can redefine the clauses:
$B := [-i]$
$E := [a, b, \beta]$
Notice that no terms may exist in $\delta$ because any term in $\delta$ can be extracted and treated as $c$ or $d$, but we defined these to not exist.
Notice the length of $E$ is shorter than the length of $A$.
This is a contradiction because the length of $A$ is given as less than $k$ while the length of $E$ is given as $k$.
Therefore this case is impossible and at least one term must exist on the R.H.S.
Consider case 2 where exactly one term exists on the R.H.S.
Recall the clauses:
$A := [a, b, \beta, i]$
$B := [c, d, \delta, -i]$
$E := [a, b, \beta, c, d, \delta]$
Recall at least one term must exist on the R.H.S., specifically either $c$ or $d$ must exist, but not both.