Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Complexity and Cryptography
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
https://www-alg.ist.hokudai.ac.jp/∼thomas/COCRB/

Lecture 9: Important Complexity Classes

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions I
First we show that a logarithmic space bound can always be
combined with a polynomial time bound.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions I
First we show that a logarithmic space bound can always be
combined with a polynomial time bound.
Theorem 1(1) L ⊆ DTISP(nO(1) , log n),(2) NL ⊆ NDTISP(nO(1) , log n),

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions I
First we show that a logarithmic space bound can always be
combined with a polynomial time bound.
Theorem 1(1) L ⊆ DTISP(nO(1) , log n),(2) NL ⊆ NDTISP(nO(1) , log n),
Proof. Let M be a k-tape TM such that SM (n) = O(log n). Thatis, there exists a constant c > 0 such that SM (n) 6 c · log n.
Recalling that a macro state consists of the head position on the
input tape, the actual state of M, and for every work tape thecontent of all cells visited as well as the actual head position,
we can bound the total number of macro states as follows:
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions IIk−1
n · |Z| |B|c·log n c · log n= O(nO(1) ) .

(1)

Here n is the number of possibilities for the head position on
the input tape. Moreover, the machine M can be in at most |Z|many different states. On each work tape, the head can havevisited at most c · log n many positions, and thus it can write
only strings of the same length on each of its work tapes. Since
we have |B| many symbols, and k − 1 many work tapes, theformula displayed above follows.
It remains to show the estimate O(nO(1) ).

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions III
Recall that
ln n
ln n
and log n =, and henceln |B|
ln 2
ln n
ln |B|
c · log n = c ·=c·· log|B| n = ĉ · log|B| n
ln 2
ln 2
log|B| n =Consequently, |B|c·log n = |B|ĉ·log|B| n = nĉ . Furthermore,
log n 6 n for n > 1, and therefore

k−1

k−1
|B|c·log n c · log n
6c · nĉ+1= ck−1 nc̃ .
for c̃ = (ĉ + 1)(k − 1). Additionally, for n > 2 there exists an msuch that nm > |Z| . Thus, the Estimate (1) is proved and thetheorem follows for the deterministic case.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions IV
For the nondeterministic case, we have additionally to take into
consideration that every polynomial is T -constructible. Hence,
the NTM M can be combined with a clock for the particularpolynomial time arising without changing the language
accepted. We leave it as an exercise to show that the amount of
space needed to implement the clock can be logarithmicallybounded. Thus, (2) follows.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions IV
For the nondeterministic case, we have additionally to take into
consideration that every polynomial is T -constructible. Hence,
the NTM M can be combined with a clock for the particularpolynomial time arising without changing the language
accepted. We leave it as an exercise to show that the amount of
space needed to implement the clock can be logarithmicallybounded. Thus, (2) follows.
The polynomial time bound just proved is essential to show thefollowing inclusion:
Theorem 2
NL ⊆ P.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions V

Proof. Let M be an NTM such that SM (n) 6 c · log n for asuitably chosen constant c > 0. We have to construct a
deterministic TM M̃ that accepts the same language as M andthat uses at most polynomial time, i.e., TM̃ (n) 6 nO(1) .
The machine M̃ works as follows:

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions VI(1) M̃ uses the same input w as M does. First, it writes all
possible macro states of M on its first work tape. By
Theorem 1 we already know that there are only
polynomially many macro states.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions VI(1) M̃ uses the same input w as M does. First, it writes all
possible macro states of M on its first work tape. By
Theorem 1 we already know that there are only
polynomially many macro states.
(2) Next, M̃ marks the one macro state of all the macro states
written on its first work tape in which M starts its
computation.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions VI(1) M̃ uses the same input w as M does. First, it writes all
possible macro states of M on its first work tape. By
Theorem 1 we already know that there are only
polynomially many macro states.
(2) Next, M̃ marks the one macro state of all the macro states
written on its first work tape in which M starts its
computation.
(3) Then, M̃ marks all macro states that can be reached in one
step by M from one of those already marked. If thisincreases the number of marked macro states, M̃ repeats
Stage (3).
Otherwise, M̃ checks whether or not there is marked
macro state in which M accepts the current input. If this is
the case, M̃ accepts the current input. Otherwise, the input
is rejected.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions VII

By construction, we directly obtain L(M) = L(M̃). Finally, there
are only polynomially many macro states to be read one time ineach execution of Stage (3). Hence, M̃ executes at most nO(1)many steps.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions VII

By construction, we directly obtain L(M) = L(M̃). Finally, there
are only polynomially many macro states to be read one time ineach execution of Stage (3). Hence, M̃ executes at most nO(1)many steps.
Note that the deterministic TM provided in the proof above
also uses nO(1) many tape cells on its work tape.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions VII

By construction, we directly obtain L(M) = L(M̃). Finally, there
are only polynomially many macro states to be read one time ineach execution of Stage (3). Hence, M̃ executes at most nO(1)many steps.
Note that the deterministic TM provided in the proof above
also uses nO(1) many tape cells on its work tape.
Next, we aim to show that NPSPACE ⊆ PSPACE. This will bedone by proving the following more general theorem:

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions VIII
Theorem 3 (Savitch (1970))
Let f(n) be an S-constructible function satisfying f(n)
 > log n.
Then, we have NSPACE(f(n)) ⊆ SPACE (f(n))2 .
We prove Savitch’s theorem in the book in a more generalcontext.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Fundamental Inclusions VIII
Theorem 3 (Savitch (1970))
Let f(n) be an S-constructible function satisfying f(n)
 > log n.
Then, we have NSPACE(f(n)) ⊆ SPACE (f(n))2 .
We prove Savitch’s theorem in the book in a more generalcontext.
So far, we have obtained the following insight:
L ⊆ NL ⊆ P ⊆ NP ⊆ NPSPACE = PSPACE .
Moreover, by Theorem 8 in Lecture 8 we also know that at least
one of the inclusions must be proper. It is conjectured that all
inclusions are proper. However, despite many efforts, so far
none of the inclusions could be proved to be proper nor could
any equality be shown.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Motivation
Question
Do there exist problems which can be considered to be the mostdifficult ones within their corresponding complexity class?

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Motivation
Question
Do there exist problems which can be considered to be the mostdifficult ones within their corresponding complexity class?
We shall prove the affirmative answer, and refer to these
problems as complete problems.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Motivation
Question
Do there exist problems which can be considered to be the mostdifficult ones within their corresponding complexity class?
We shall prove the affirmative answer, and refer to these
problems as complete problems.
The importance of complete problems is easily explained. The
efficient solution of a complete problem for NL or NP could be
used to efficiently solve all of the problems in NL or NP,
respectively.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Motivation
Question
Do there exist problems which can be considered to be the mostdifficult ones within their corresponding complexity class?
We shall prove the affirmative answer, and refer to these
problems as complete problems.
The importance of complete problems is easily explained. The
efficient solution of a complete problem for NL or NP could be
used to efficiently solve all of the problems in NL or NP,
respectively.
Next, we have to modify the deterministic TM model in a way
such that strings can be computed as output. We use Σ todenote any fixed finite alphabet and Σ∗ for denoting the freemonoid over Σ.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions I
Definition 1
A function f : Σ∗ → Σ∗ is said to be log-space computable if there
exists a deterministic TM Mf satisfying the following
properties:(1) Mf possesses an input tape with a two-way read-only
head, an output tape with a one-way write-only head andfinitely many work tapes each of which has a two-way
read-write head.
(2) On input w the machine Mf computes f(w) and writes it
on its output tape. While performing this computation, Mf
uses on each of its work tapes at most O(log |w|) many tapecells.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions II
Log-space computable functions have an interesting property
which is stated as an exercise.
Exercise 1. Show that for each log-space computable function thecondition |f(w)| 6 |w|O(1) is satisfied.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions II
Log-space computable functions have an interesting property
which is stated as an exercise.
Exercise 1. Show that for each log-space computable function thecondition |f(w)| 6 |w|O(1) is satisfied.
Next, we define reductions.
Definition 2
Let A, B ⊆ Σ∗ be any two decidable languages. The language A
is said to be log-space reducible to the language B (abbr. A 6log B)
if there exists a log-space computable function f such that for allw ∈ Σ∗ the condition w ∈ A if and only if f(w) ∈ B is satisfied.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions II
Log-space computable functions have an interesting property
which is stated as an exercise.
Exercise 1. Show that for each log-space computable function thecondition |f(w)| 6 |w|O(1) is satisfied.
Next, we define reductions.
Definition 2
Let A, B ⊆ Σ∗ be any two decidable languages. The language A
is said to be log-space reducible to the language B (abbr. A 6log B)
if there exists a log-space computable function f such that for allw ∈ Σ∗ the condition w ∈ A if and only if f(w) ∈ B is satisfied.
Exercise 2. Let L1 , L2 , L3 ⊆ Σ∗ be any decidable languages. Then
we have: If L1 6log L2 and L2 6log L3 then L1 6log L3 , i.e., log-space
reducibility is transitive.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions III
Now, we are ready to define the notions of hardness andcompleteness.
Definition 3
Let S be a family of decidable languages over Σ∗ and let L0 be alanguage such that L0 ⊆ Σ∗ . The language L0 is said to belog-space hard for S if L 6log L0 for every language L ∈ S.
If additionally L0 ∈ S is satisfied then the language L0 is said tobe log-space complete for S.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions III
Now, we are ready to define the notions of hardness andcompleteness.
Definition 3
Let S be a family of decidable languages over Σ∗ and let L0 be alanguage such that L0 ⊆ Σ∗ . The language L0 is said to belog-space hard for S if L 6log L0 for every language L ∈ S.
If additionally L0 ∈ S is satisfied then the language L0 is said tobe log-space complete for S.
Next, we ask in which sense a language A ⊆ Σ∗ is easier than alanguage B ⊆ Σ∗ provided A 6log B. This is done via thefollowing lemma:

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions IV

Lemma 1Let M be a TM such that SM (n) , o(log n). If a language L ⊆ Σ∗ isf such that
log-space reducible to L(M) then there exists a TM M
f
L = L(M) and SM
f (n) = O(SM (n)).

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions IV

Lemma 1Let M be a TM such that SM (n) , o(log n). If a language L ⊆ Σ∗ isf such that
log-space reducible to L(M) then there exists a TM M
f
L = L(M) and SM
f (n) = O(SM (n)).
Proof. The proof idea is to combine the acceptor TM M with a
TM Mf that realizes the log-space translation of L into L(M).
But there is a problem. The space bound of M does not allow,
in general, to write the result f(w) of the translation of w via
Mf on M’s work tape(s). Hence, we have to modify Mfappropriately. We define a deterministic TM Mf0 as follows:

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions V
On input w and input bin(k) on an auxiliary work tape, Mf0
works as Mf does but writes only the kth symbol of f(w) on its
output tape. Since |f(w)| 6 |w|O(1) the space bound O(log n)for Mf0 is ensured. The TM Mf0 can count all attempts of Mf towrite a symbol on its output tape until the kth one is reachedwhich is then executed.
Finally, M is modified in way such that each change of the head
position on the input tape of M is accompanied by setting thebinary counter to the actual input head position and bycomputing the symbol to be read by executing Mf0 on input w
and bin(k) as described above.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions V
On input w and input bin(k) on an auxiliary work tape, Mf0
works as Mf does but writes only the kth symbol of f(w) on its
output tape. Since |f(w)| 6 |w|O(1) the space bound O(log n)for Mf0 is ensured. The TM Mf0 can count all attempts of Mf towrite a symbol on its output tape until the kth one is reachedwhich is then executed.
Finally, M is modified in way such that each change of the head
position on the input tape of M is accompanied by setting thebinary counter to the actual input head position and bycomputing the symbol to be read by executing Mf0 on input w
and bin(k) as described above.
Please note that the condition SM (n) , o(log n) was essential
for proving the latter lemma, since otherwise we could nothave used the binary counter.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions VI
Lemma 1 allows for the following corollary:
Corollary 1
Let L, L 0 ⊆ Σ∗ be any languages.
(1) If L ∈ L and L 0 6log L then L 0 ∈ L.
(2) If L ∈ L and ∅ , L 0 , Σ∗ then L 6log L 0 .
Proof. We leave it as an exercise to prove this corollary.
Consequently, L constitutes the lowest level of log-space
reducibility.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Remarks
It should also be noted that there are a couple of reducibility
notions around which have been intensively studied in theliterature. We mention here only polynomial-time reducibility
which is defined analogously as log-space reducibility.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Remarks
It should also be noted that there are a couple of reducibility
notions around which have been intensively studied in theliterature. We mention here only polynomial-time reducibility
which is defined analogously as log-space reducibility.
The only difference to Definition 2 is that the function f is now
only required to be computable by a deterministic TM obeyinga polynomial time bound for its computation time instead ofthe log-space bound required in Definition 1. If a language L1 ispolynomial-time reducible to a language L2 then we write
L1 6poly L2 .

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Remarks
It should also be noted that there are a couple of reducibility
notions around which have been intensively studied in theliterature. We mention here only polynomial-time reducibility
which is defined analogously as log-space reducibility.
The only difference to Definition 2 is that the function f is now
only required to be computable by a deterministic TM obeyinga polynomial time bound for its computation time instead ofthe log-space bound required in Definition 1. If a language L1 ispolynomial-time reducible to a language L2 then we write
L1 6poly L2 .
For getting a better understanding of polynomial-time
reducibility, we recommend to solve the following exercise:Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions VII
Exercise 3. Let L1 , L2 be any two languages. If L1 6log L2 thenL1 6poly L2 .
The notion of reducibility also allows one to define anequivalence relation.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Reductions VII
Exercise 3. Let L1 , L2 be any two languages. If L1 6log L2 thenL1 6poly L2 .
The notion of reducibility also allows one to define anequivalence relation.
Definition 4
Let L1 , L2 ⊆ Σ∗ be any two decidable languages. The languages
L1 and L2 are said to be equivalent with respect to log-space
reducibility (polynomial-time reducibility) if L1 6log L2 andL2 6log L1 (L1 6poly L2 and L2 6poly L1 ).
If L1 and L2 are equivalent with respect to log-space reducibility
and polynomial-time reducibility then we write L1 ≡log L2and L1 ≡poly L2 , respectively.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP I
Our next goal is to establish the existence of complete problems
for the complexity class NL defined in the last lecture.
For that purpose, we define the graph accessibility problem(abbr. GAP).
GAP
Input: A directed graph G = (V, E) with vertex set
V = {v1 , . . . , vm } and a distinguished start node vs and a
distinguished end node ve .
Problem: Does there exist a path between vs and ve ?
If the graph G is given by its adjacency-list, then the input
length n of GAP can be bounded by O(m2 log m). Moreover,
we can safely assume n > m.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP II

Next, we show GAP to be NL-complete. This is done in two
steps; i.e., by first showing GAP to be NL-hard and then GAP
to be in NL.
Lemma 2GAP is NL-hard.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP II

Next, we show GAP to be NL-complete. This is done in two
steps; i.e., by first showing GAP to be NL-hard and then GAP
to be in NL.
Lemma 2GAP is NL-hard.
Proof. Let M be a TM such that SM (n) ∈ O(log n) and let w be
an input to M. We define a graph Gw = (V, E) as follows:

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP III
The nodes of Gw are all the macro states of M that can occur
under the space bound SM (|w|). Let v and v 0 be any two macrostates of M (i.e., any two nodes of Gw ). We define (v, v 0 ) ∈ E iff
M can reach macro state v 0 from macro state v in one step.
Without loss of generality, we can assume that the macro stateat the beginning of M’s computation on input w is uniquelydetermined. Also without loss of generality, we can assume
that, if M accepts w, then the accepting macro state of M isuniquely determined, too.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP III
The nodes of Gw are all the macro states of M that can occur
under the space bound SM (|w|). Let v and v 0 be any two macrostates of M (i.e., any two nodes of Gw ). We define (v, v 0 ) ∈ E iff
M can reach macro state v 0 from macro state v in one step.
Without loss of generality, we can assume that the macro stateat the beginning of M’s computation on input w is uniquelydetermined. Also without loss of generality, we can assume
that, if M accepts w, then the accepting macro state of M isuniquely determined, too. Now, it is easy to see that the graph
Gw is log-space computable from input w, since the number ofnodes is uniformly polynomially bounded in |w|. If the nodes of
Gw are appropriately numbered, then our construction impliesw ∈ L(M) ⇐⇒ Gw ∈ GAP .
So, every language from NL is log-space reducible to GAP.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP IV
Next, we show GAP to be acceptable by an NTM.
Lemma 3
GAP ∈ NL.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP IV
Next, we show GAP to be acceptable by an NTM.
Lemma 3
GAP ∈ NL.
Proof. Let any graph G = (V, E) with vertex set V = {v1 , . . . , vm }and a distinguished start node vs and a distinguished end nodeve be given as input. Let n be the length of the input. As shown
above, n can be bounded by O(m2 log m). Thus, the spacebound log n is sufficient to store any node number in binary.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP IV
Next, we show GAP to be acceptable by an NTM.
Lemma 3
GAP ∈ NL.
Proof. Let any graph G = (V, E) with vertex set V = {v1 , . . . , vm }and a distinguished start node vs and a distinguished end nodeve be given as input. Let n be the length of the input. As shown
above, n can be bounded by O(m2 log m). Thus, the spacebound log n is sufficient to store any node number in binary.
The NTM M works as follows: First, it stores the number s ofthe start node vs . Then, non-deterministically any successorof vs , say vi , is chosen (that is, (vs , vi ) ∈ E), s is erased, and thenumber i is stored as actual node number.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

GAP V

Next, the process is iterated. That is, assuming j to be the actual
node number, any successor of vj , say vk , is chosen and its
number k is stored as actual node number and j is erased. The
storing and erasing is done in a way such that the total amountof space used by M is O(log n).

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

GAP V

Next, the process is iterated. That is, assuming j to be the actual
node number, any successor of vj , say vk , is chosen and its
number k is stored as actual node number and j is erased. The
storing and erasing is done in a way such that the total amountof space used by M is O(log n).
The graph G is accepted, if e is reached as actual node number.
Otherwise, G is not accepted.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

GAP V

Next, the process is iterated. That is, assuming j to be the actual
node number, any successor of vj , say vk , is chosen and its
number k is stored as actual node number and j is erased. The
storing and erasing is done in a way such that the total amountof space used by M is O(log n).
The graph G is accepted, if e is reached as actual node number.
Otherwise, G is not accepted.
Clearly, if there is a path from vs to ve in G, then there is anaccepting computation of M on input G. Otherwise, nocomputation can accept G.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP VIBy Definition 3, the Lemmata 2 and 3 directly imply thefollowing corollary:
Corollary 2
GAP is NL-complete.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP VIBy Definition 3, the Lemmata 2 and 3 directly imply thefollowing corollary:
Corollary 2
GAP is NL-complete.
Moreover, we immediately obtain the following corollary:
Corollary 3
Let f(n) , o(log n) be a space bounding function. Then we have
GAP ∈ SPACE(f(n)) if and only if NL ⊆ SPACE(f(n)).

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

GAP VIBy Definition 3, the Lemmata 2 and 3 directly imply thefollowing corollary:
Corollary 2
GAP is NL-complete.
Moreover, we immediately obtain the following corollary:
Corollary 3
Let f(n) , o(log n) be a space bounding function. Then we have
GAP ∈ SPACE(f(n)) if and only if NL ⊆ SPACE(f(n)).
Further NL-complete problems are studied in the book.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems I
Now, we turn our attention to the class NP which contains
many important problems. We start with a list of examples for
decision problems that turn out to be all in NP. We define these
problems here as languages and assume any reasonableencoding of the input.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems I
Now, we turn our attention to the class NP which contains
many important problems. We start with a list of examples for
decision problems that turn out to be all in NP. We define these
problems here as languages and assume any reasonableencoding of the input.
Let G = (V, E) be an undirected graph. A complete subgraph ofsize k of G is said to be a k-Clique. Here a graph is said to becomplete if every vertex is connected to any other vertex. We set
CLIQUE = {(G, k) | G possesses a k-Clique} .

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems I
Now, we turn our attention to the class NP which contains
many important problems. We start with a list of examples for
decision problems that turn out to be all in NP. We define these
problems here as languages and assume any reasonableencoding of the input.
Let G = (V, E) be an undirected graph. A complete subgraph ofsize k of G is said to be a k-Clique. Here a graph is said to becomplete if every vertex is connected to any other vertex. We set
CLIQUE = {(G, k) | G possesses a k-Clique} .
Let G = (V, E) be an undirected graph. A set U ⊆ V is said to be
independent if (u, v) < E for all u, v ∈ U, u , v. We set
INDSET = {(G, k) | G possesses an independent set of size k} .
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems II

Now, let G = (V, E) be a directed graph. A Hamiltonian path is apath visiting all vertices of G exactly ones. We set
dHAMILTON = {G | G possesses a Hamiltonian path} .

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems II

Now, let G = (V, E) be a directed graph. A Hamiltonian path is apath visiting all vertices of G exactly ones. We set
dHAMILTON = {G | G possesses a Hamiltonian path} .
A vertex cover of an undirected graph G = (V, E) is a subset
V 0 ⊆ V such that if (u, v) ∈ E, then u ∈ V 0 or v ∈ V 0 . The size ofa vertex cover V 0 is the cardinality of V 0 . We set
VCOVER = {(G, k) | G possesses a vertex cover of size k} .

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems III

Subset Sum Problem
Input: a number M and a vector (a0 , . . . , an−1 ) ∈ Nn .
Problem: Decide whether there exists a vectorn−1P(b0 , . . . , bn−1 ) ∈ {0, 1}n such that M =aj bj .
j=0

As with any arithmetic problem, it is important to recall thatthe input integers are coded in binary. Then we define
SUBSUM to be the language of all subset sum problems((a0 , . . . , an−1 ), M) for which there is a vectorn−1P(b0 , . . . , bn−1 ) ∈ {0, 1}n such that M =aj bj .
j=0

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems IV
Finally, we define the famous satisfiability problem.
Definition 5
Let F = f(x1 , . . . , xn ) be a Boolean formula consisting of thevariables x1 , . . . , xn and the Boolean operators ∨, ∧, ¬. F is said
to be satisfiable if there exists an assignment (a1 , . . . , an ) ∈ {0, 1}nto the variables x1 , . . . , xn such that F(a1 , . . . , an ) = 1.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems IV
Finally, we define the famous satisfiability problem.
Definition 5
Let F = f(x1 , . . . , xn ) be a Boolean formula consisting of thevariables x1 , . . . , xn and the Boolean operators ∨, ∧, ¬. F is said
to be satisfiable if there exists an assignment (a1 , . . . , an ) ∈ {0, 1}nto the variables x1 , . . . , xn such that F(a1 , . . . , an ) = 1.
The satisfiability problem is then the language
SAT = {F | F is a satisfiable formula}.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems V
Let us ask what all the languages defined above do have incommon. The general pattern is that it is presumably very hard
to find a witness that any of its instances belongs to them. For
example, in order to find a satisfying assignment one may haveto try all possible assignments, i.e., all 2n many Boolean vectors
a1 , . . . , an ∈ {0, 1}n . The same clearly applies for SUBSUM.
As for dHAMILTON, one may be forced to try all n!
permutations of the vertices of G = (V, E), where |V| = n inorder to find a Hamiltonian path.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems V
Let us ask what all the languages defined above do have incommon. The general pattern is that it is presumably very hard
to find a witness that any of its instances belongs to them. For
example, in order to find a satisfying assignment one may haveto try all possible assignments, i.e., all 2n many Boolean vectors
a1 , . . . , an ∈ {0, 1}n . The same clearly applies for SUBSUM.
As for dHAMILTON, one may be forced to try all n!
permutations of the vertices of G = (V, E), where |V| = n inorder to find a Hamiltonian path.
On the other hand, it is for all the languages given above easy
to check whether or not a witness is given. For instance, for any
given assignment one can quickly check whether or not it issatisfying a given Boolean formula by a deterministic TM.
Informally, this property may serve as a rule of thumb for
deciding whether or not any given language belongs to NP.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems VI
Next, we ask whether or not the class NP contains an
NP-complete language. The affirmative answer has been given
by Cook (1971) and Levin (1973), who could show thefollowing important theorem:
Theorem 4 (Cook (1971), Levin (1973))
SAT is NP-complete.
We are not going to prove this theorem here, since there aremany proofs in the literature. Furthermore, there is no need toprove any problem to be NP-complete by using Cook’s (1971)
original proof technique.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems VI
Next, we ask whether or not the class NP contains an
NP-complete language. The affirmative answer has been given
by Cook (1971) and Levin (1973), who could show thefollowing important theorem:
Theorem 4 (Cook (1971), Levin (1973))
SAT is NP-complete.
We are not going to prove this theorem here, since there aremany proofs in the literature. Furthermore, there is no need toprove any problem to be NP-complete by using Cook’s (1971)
original proof technique.
Instead, to show the NP-completeness of any other language L
it suffices to reduce SAT or any other language known to be
NP-complete to L.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems VII
Next, we exemplify this proof technique here.
A formula F is said to be in `-CNF form if F is in conjunctive
normal form and each clause contains precisely ` literals.
Let `-SAT be the language of all satisfiable formulae in `-CNF
form. Then, we can show the following:
Theorem 5`-SAT is NP-complete for all ` > 3.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems VII
Next, we exemplify this proof technique here.
A formula F is said to be in `-CNF form if F is in conjunctive
normal form and each clause contains precisely ` literals.
Let `-SAT be the language of all satisfiable formulae in `-CNF
form. Then, we can show the following:
Theorem 5`-SAT is NP-complete for all ` > 3.
Proof. Since SAT is in NP we have `-SAT ∈ NP, too. Thus, itsuffices to log-space reduce SAT to `-SAT.
First, we show that any formula F can be transformed into asat-equivalent formula F 0 in CNF. Here by sat-equivalent wemean that F is satisfiable iff F 0 is satisfiable.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems VIII
Note that we cannot just transform F into its CNF, since thelength of the CNF may be exponential in the length of F, thus
violating our requirement to log-space reduce SAT to `-SAT.
For obtaining the desired transformation of F into asat-equivalent formula F 0 in CNF, in general we need new
auxiliary variables. Here by new we mean that these variables
do not occur in F. We proceed as follows: In our first step wetransform F into a logical equivalent formula F 0 by using deMorgan’s rules as well as ¬¬x ≡ x. Note the we use both ¬x
and x to denote negation.
Step 1. Using de Morgan’s rules, we transform F into F 0 suchthat all negations in F 0 appear at the variables.
After a bit of reflection it is easy to see that Step 1 can berealized in log-space.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems IX
Let F 0 be the formula obtained so far. Next, we transform F 0
into a sat-equivalent CNF by using the following observation:
If F 0 = F1 ∨ F2 and F1 , F2 are already in CNF, then we canreplace F 0 by
(F1 ∨ y) ∧ (F2 ∨ y) ,where y is a new variable. Clearly, the new formula issat-equivalent to F 0 . We refer to this rule as to Rule 1.
Furthermore, we need Rule 2 displayed below to transformF1 ∨ y and F2 ∨ y into a CNF. This is done as follows: Let
Fi = G1 ∧ G2 ∧ . . . ∧ Gk . Then Fi ∨ yα is equivalent to(G1 ∨ yα ) ∧ (G2 ∨ yα ) ∧ . . . ∧ (Gk ∨ yα ) ,and we have again a conjunction of clauses.
Step 2. Apply Rules 1 and 2 recursively until a CNF is obtained.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems X
Next, we have to show that any formula in CNF can betransformed into a sat-equivalent formula in `-CNF form. For
the sake of presentation we handle here the case ` = 3, only.
Consider any clause C = (z1 ∨ · · · ∨ zk ). In dependence on k wereplace C by the following formula by using new variables yi :k = 1 : (z1 ∨ y1 ∨ y2 ) ∧ (z1 ∨ y1 ∨ y2 ) ∧ (z1 ∨ y1 ∨ y2 ) ∧ (z1 ∨ y1 ∨ y2 )k = 2 : (z1 ∨ z2 ∨ y1 ) ∧ (z1 ∨ z2 ∨ y1 )k = 3 : (z1 ∨ z2 ∨ z3 ) i.e., we do not change C
k > 3 : (z1 ∨ z2 ∨ y1 ) ∧ (y1 ∨ z3 ∨ y2 ) ∧ (y2 ∨ z4 ∨ y3 )∧. . . ∧ (yk−4 ∨ zk−2 ∨ yk−3 ) ∧ (yk−3 ∨ zk−1 ∨ zk ) =: C̃ .

Clearly, these formulae can be computed in log-space.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XI

The sat-equivalence of the formulae obtained can be seen as
follows: In case k = 1, the four clauses can be simultaneously
satisfied if and only if z1 is assigned the value 1, since
independently of the assignments for y1 , y2 , in one of the fourclauses the resulting evaluation is 0.
Analogously, one directly sees that in case k = 2 the two clauses
can be simultaneously satisfied if and only if z1 or z2 is assigned
the value 1.
For k = 3 nothing has to be shown.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XII
Finally, for k > 3 it remains to show that C is satisfiable if andonly if C̃ is satisfiable.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XII
Finally, for k > 3 it remains to show that C is satisfiable if andonly if C̃ is satisfiable.
Assume (z1 ∨ · · · ∨ zk ) is satisfied by zi = 1. If i = 1 or i = 2,
then we set yj = 0 for all j = 1, . . . , k − 3. So, the first clause in C̃is satisfied by z1 or z2 and all remaining clauses in C̃ aresatisfied by yj , j = 1, . . . , k − 3.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XII
Finally, for k > 3 it remains to show that C is satisfiable if andonly if C̃ is satisfiable.
Assume (z1 ∨ · · · ∨ zk ) is satisfied by zi = 1. If i = 1 or i = 2,
then we set yj = 0 for all j = 1, . . . , k − 3. So, the first clause in C̃is satisfied by z1 or z2 and all remaining clauses in C̃ aresatisfied by yj , j = 1, . . . , k − 3.
If i > 3, then we set y1 = y2 = · · · = yi−2 = 1,
yi−1 = yi = · · · yk−3 = 0. Now, by construction, in C̃ the firsti − 2 clauses are satisfied by by the yi , the (i − 1)st clause(containing zi ) is clearly satisfied by z1 , and the remainingk − (i − 2) − 3 clauses in C̃ are satisfied by yi .

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XIII

Next, assume C̃ to be satisfied. We distinguish the following 3
cases: If all yj = 0, then zk−1 ∨ zk must evaluate to 1, thus also
C is satisfied. Analogously, if all yj = 1, then z1 ∨ z2 mustevaluate to 1, and hence C is satisfied, too.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XIII

Next, assume C̃ to be satisfied. We distinguish the following 3
cases: If all yj = 0, then zk−1 ∨ zk must evaluate to 1, thus also
C is satisfied. Analogously, if all yj = 1, then z1 ∨ z2 mustevaluate to 1, and hence C is satisfied, too.
It remains to consider the case that up to some i, 1 6 i < k − 3
we have y1 = · · · = yi = 1 and yi+1 = 0. Now, the (i + 1)stclause of C̃ can evaluate to 1 if and only if zi+2 = 1, that is, C isagain satisfied.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XIV
The importance of 3-SAT is its simple combinatorial structure
which allows to apply it to prove the NP-completeness of manyother problems as shown below. Note that the condition ` > 3
is essential.
Exercise 4. Prove or disprove 2-SAT ∈ P.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XIV
The importance of 3-SAT is its simple combinatorial structure
which allows to apply it to prove the NP-completeness of manyother problems as shown below. Note that the condition ` > 3
is essential.
Exercise 4. Prove or disprove 2-SAT ∈ P.
Next, by reducing 3-SAT to CLIQUE one can easily prove thefollowing theorem:
Theorem 6
CLIQUE is NP-complete.
The proof is given in the book.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XVHaving shown CLIQUE to be NP-complete directly allows toprove VCOVER to be NP-complete, too.
Theorem 7
VCOVER is NP-complete.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XVHaving shown CLIQUE to be NP-complete directly allows toprove VCOVER to be NP-complete, too.
Theorem 7
VCOVER is NP-complete.
Proof. It is easy to see that VCOVER ∈ NP. Next, we reduce
CLIQUE to VCOVER. The reduction is almost trivial. Let
G = (V, E) and k be given. We map G to its complement graph
G = (V, E), where E = {(u, v) | u, v ∈ V, u , v, (u, v) < E}.
Furthermore, k is mapped to |V| − k. We omit the details.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

NP-complete Problems XVHaving shown CLIQUE to be NP-complete directly allows toprove VCOVER to be NP-complete, too.
Theorem 7
VCOVER is NP-complete.
Proof. It is easy to see that VCOVER ∈ NP. Next, we reduce
CLIQUE to VCOVER. The reduction is almost trivial. Let
G = (V, E) and k be given. We map G to its complement graph
G = (V, E), where E = {(u, v) | u, v ∈ V, u , v, (u, v) < E}.
Furthermore, k is mapped to |V| − k. We omit the details.
Exercise 5. Show SUBSUM to be NP-complete.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

ExampleExample 6
F = ¬(¬(x1 ∨ x2 ∨ x3 ) ∧ (x4 ∨ (x3 ∧ x5 ))).
Then, in Step 1, by using ¬(β1 ∧ β2 ) ≡ ¬β1 ∨ ¬β2 or¬(β1 ∨ β2 ) ≡ ¬β1 ∧ ¬β2 we successively obtain:¬(¬(x1 ∨ x2 ∨ x3 ) ∧ (x4 ∨ (x3 ∧ x5 )))≡ ¬¬(x1 ∨ x2 ∨ x3 ) ∨ ¬(x4 ∨ (x3 ∧ x5 ))≡ (x1 ∨ x2 ∨ x3 ) ∨ ¬(x4 ∨ (x3 ∧ x5 ))≡ (x1 ∨ x2 ∨ x3 ) ∨ (x4 ∧ ¬(x3 ∧ x5 ))≡ (x1 ∨ x2 ∨ x3 ) ∨ (x4 ∧ (x3 ∨ x5 )) .

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

Example continued

Continuing our example, we thus obtain (where ∼ denotes
sat-equivalence)(x1 ∨ x2 ∨ x3 ) ∨ (x4 ∧ (x3 ∨ x5 ))∼ (x1 ∨ x2 ∨ x3 ∨ y1 ) ∧ (x4 ∨ y1 ) ∧ (x3 ∨ x5 ∨ y1 ) .

Complexity and Cryptography(2)c Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

Example continued

We finish our example here for the case of 3-CNF.
So, we have to apply the rules for k > 3 and k = 2. Applying
the rule for k > 3 requires the introduction of a new variable y2
and applying the rule for k = 2 requires the introduction of a
new variable y3 . Thus, we finally obtain.
(x1 ∨ x2 ∨ x3 ∨ y1 ) ∧ (x4 ∨ y1 ) ∧ (x3 ∨ x5 ∨ y1 )∼(x1 ∨ x2 ∨ y2 ) ∧ (y2 ∨ x3 ∨ y1 ) ∧ (x4 ∨ y1 ∨ y3 ) ∧ (x4 ∨ y1 ∨ y3 )∧ (x3 ∨ x5 ∨ y1 ) .

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Final Remarks I

As already mentioned, so far we do not know whether or not
P = NP. Resolving this problem remains a huge challenge.
So, let us shortly discuss consequences of the two possible
answers. If P , NP, then not much will change, since thisconjecture is favored by many scientists. The main change, ofcourse, is then the switch from conjecture to theorem, and all
the theorems having a “. . . if P , NP” in their statement would
be unconditionally true.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Final Remarks II
What are the consequences if we could prove that P = NP?
Clearly this result would be also of fundamental
epistemological importance. But the practical consequences
may vary. If, for some important NP-complete problem like
3-SAT someone finds a very efficient algorithm, say having
running time O(n2 ), then the practical consequences would beheaven and hell at the same time. Heaven for those who needto find quickly solutions for NP-complete problems, e.g., formany AI applications, for VLSI designers, for engineers.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Final Remarks II
What are the consequences if we could prove that P = NP?
Clearly this result would be also of fundamental
epistemological importance. But the practical consequences
may vary. If, for some important NP-complete problem like
3-SAT someone finds a very efficient algorithm, say having
running time O(n2 ), then the practical consequences would beheaven and hell at the same time. Heaven for those who needto find quickly solutions for NP-complete problems, e.g., formany AI applications, for VLSI designers, for engineers.
On the other hand, all tools currently in use for privacy
protection, e.g., SSL, RSA, or PGP will become useless overnight. Also, much of what mathematician are doing could thenbe done by a machine performing efficient theorem proving.
Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Final Remarks III

But it is also possible that the best polynomial time algorithm
for any NP-complete problem has a running time of orderO(nc ), where c is a six digit number, or even a 1000000 digit
number. Of course, in this case the practical consequences
would be much less dramatic, since the NP-complete problems
remain hard to solve for larger inputs. If the latter would betrue, this would also explain why we have not found any suchalgorithm yet.
Last but not least, if P = NP then randomization would notprovide any principal gain.

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

RemarksEnd

Thank you!

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

NP-completenessl-SATISFIABILITY

Remarks

End

Walter J. Savitch

Complexity and Cryptographyc Thomas Zeugmann

Inclusions

Completeness

GAP

Steven A. Cook

Complexity and Cryptography

NP-completenessl-SATISFIABILITY

Remarks

End

Leonid Levinc Thomas Zeugmann