1.Theory of Computing
Lecture 19
MAS 714
Hartmut Klauck
2.Subset Sum
Input: set S of natural numbers, target t
Is there a subset S’µ S such that the elements in S’ sum to t?
Theorem: Subset Sum is NP-complete
Reduction from 3-SAT
3.Subset Sum
Given formula of m clauses and n variables
no variable is unused, xi and :xi not in same clause
Create 2 numbers for each variable: vi, wi
2 numbers for each clause: rc, sc
Numbers are base 10 and have n+m digits
t: 1 in each variable digit and 4 in each clause digit
vi: 1 at digit i and 1 for each clause digit with literal xi
wi: 1 at digit i and 1 for each clause digit with literal :xi
rc: 1 at clause digit c
sc: 2 at clause digit c
4.Subset Sum
Suppose sum of a subset of numbers equals t
Clearly: cannot contain both vi and wi
Set xi=1 iff vi is in the subset
Claim: Satisfying for F
rc and sc can contribute at most 3 to a clause digit, but the sum is 4, hence the vi or wi in the subset must have digit 1 for the clause-> clause in F is satisfied
5.Subset Sum
Suppose there is a satisfying assignment to F
If xi=1 take vi into the subset, else wi
Sums all numbers, consider n most significant digits: all are 1
Consider the last m digits of the sum:
For each clause digit value is at least 1, and up to 3
Add appropriate numbers rc, sc to make the sum equal to t
6.3-Dimensional Matching
X,Y,Z are sets of n elements each
E is a subset of X£ Y£ Z
A 3D-matching is a set of triples that do not share vertices
Question: Is there a perfect matching, i.e., one that contains every vertex in exactly one edge?
Recall: 2D-matching is in P
7.NP-hardness
We reduce from 3-SAT
Formula F with n variables and m clauses
Variable gadget for xi:Vertices: {ai,1,…,ai,2m } [{bi,1,...,bi,2m }
Edges: (ai,j, ai,j+1, bi,j)
In a perfect matching only bi,j for odd j or for even j can be present (else some ai,j covered twice)
Covering even bi,j means xi=1
8.3DM
Clause gadget:
Vertices {cj, dj}
Edges: connect clause gadget nodes with variable gadgets: literal xi: connect with bi,2j, else with bi,2j-1
Observation: Must choose exactly one edge per clause gadget. This covers an odd or even bi,j vertex. Can cover a-vertices only if either odd or even bi,j are used, not both.
More details: Need some extra gadgets to cover unused b-vertices
9.3DM
Suppose F is satisfiable.
Choose the edges for the variable gadgets as in x
Then for a clause (l1Ç l2Ç l3) all true literals have un-covered b-vertices that can be covered using an edge that covers the clause gadget vertices
Similarly, given a perfect matching we can find a satisfying assignment
10.co-NP
co-NP is the class of complements of languages that are in NP
It is widely believed that NP co-NP
This would imply that NPÅco-NP does not contain NP-complete problems
Example: IntegerFactorization (decision version)
We don’t know a polynomial time algorithm, but the problem is likely not NP-complete
11.Intermediate Problems
Ladner’s Theorem
Unless P=NP, there exist problems in NP that are neither in P nor NP-complete
Candidate problems (their decision versions):
Integer Factorization
Graph Isomorphism
Discrete Logarithm
Group Isomorphism
Finding approximate short vectors in lattices
Some of these problems can be used to define public key cryptosystems
Such systems are hard to break if the underlying problems are hard (e.g. for factorization/discrete log)
12.Other completeness notions
P-completeness
Reductions must be computed in logarithmic space
implies (probably) that a problem cannot be solved in space polylog n or parallel time polylog n
EXP-completeness
Implies that the problem cannot be solved in polynomial time
NEXP-completeness
Problem is not in NP
PSPACE-completeness
Problem is likely not in NP
Many two-player games like generalized chess with time bound
13.New topic: Computability
Question 1: Are all Boolean functions computable?
Answer 1: yes, by Boolean circuit families
But those are not uniform, seems like cheating, circuit family is an infinite object
Question 2: Are all languages Lµ {0,1}* computable by Turing machines ?
Answer 2: NO.
14.Argument number 1
A Turing machine can be described by a finite string
list the elements of the 8-tuple
Alternative: C++ program
We can identify finite strings with natural numbers
treat each character as a digit
Conclusion: there are infinitely many Turing machines, but the set of all Turing machines is countable
A set S is countable if there is an injective mapping from S to the natural numbers
An infinite, countable set has the same cardinality as the natural numbers
Example: the rational numbers are countable, the reals are not
15.Argument number 1
Theorem: the set of languages Lµ{0,1}* is uncountable
Indeed has the same cardinality as the real numbers
Conclusion:
Almost all languages are not computable by a TM
No matter how much time the TM can spend computing
16.Proof of the theorem
First we use Cantor’s method of diagonalization to show that there is a language that cannot be computed
Let M1, M2,… denote an enumeration of all Turing machines
Let x1, x2,… denotes an enumeration of all inputs in {0,1}*
Consider the matrix A that has rows labeled by xi and columns labeled by Mj and that contains 1 if Mj accepts xi and 0 otherwise
17.Proof of the claim
Each column j corresponds to the language of strings accepted by Mj
Consider the complement of the diagonal of A
0 with 1 and vice versa
Consider the language L that contains string xi iff the i-th diagonal element is 0
L is not equal to any of the languages computed by the Mj !
Hence L is an un-computable language
[For languages we use both terms computable/decidable to mean that the language can be decided by a TM that halts on all inputs]
18.Proof of the claim
The same can be done if we replace the columns with any enumeration of languages
Hence the set of all languages is not countable, i.e., there is no injective mapping from the set of all languages to the natural numbers
Note: the set of all languages has the same cardinality as the reals
Find an injective mapping from the reals to the set of all languages
This means that `almost all’ languages are not computable
But what about an explicit example?
19.Universality
To answer this question we need another property of Turing machine
Universality means that there is a Turing machine that can simulate all other Turing machines
Compare: actual computers are universal, we generally don’t buy/build a new computer for a new application
20.Universality
Fix some way to encode Turing machines
Write for the encoding of TM M (as a string)
Definition: A universal Turing machine is a TM that on input ,x accepts if and only if M accepts on x
Theorem: There is a universal TM U
21.Proof
Note: Since U must be finite, we cannot simply read into the internal state of U
in fact we cannot even read a state of M into U’s internal state
Copy input x to a second tape (we assume that M has 1 tape)
A third tape contains the current state of M
w.l.o.g. this is 02Q
We need to show that one step of M can be simulated
Idea: search the transition function table in to determine the new state given the tape symbol on tape 2 and the current state on tape 3, update both, move the head on tape 2
Each step tests if the current state is accepting/rejecting
We have a machine U that can simulate any 1-tape TM using 3 tapes
Running time: we are interested in the running time in terms of |x|
Fact: a universal TM U with time O(C n log n) exist, where C depends on M, and U has the same number of tapes as M
22.Halting Problem
On an input x, a machine M might not halt
Infinite loop
It would be nice to be able to decide if this happens!
HALT={,x: M halts on input x}
Theorem:
HALT is not computable
23.Proof
We try a similar argument to Cantor’s
Consider a TM H that decides HALT
halts on all inputs and gives the correct output
Consider inputs ,
These belong to HALT, if M halts on its encoding
We define a new machine M that does the following:
On input x, run H on x,x [use U, note that H halts]
If H reports that x halts on x , go into an infinite loop
Else halt
24.Proof
What does M do on ?
If M halts on , H will say so, and M will go into an infinite loop on
If M does not halt on , then H will say it does not halt, and M will halt on
Contradiction!
Hence H does not exist!
25.Reductions
Definition: L many-one reduces to S is there is a computable function f such that x2L , f(x)2 S
Notation: L· S
Conclusion: if L is not decidable then S is not decidable
More general notion of reductions: Turing reductions (using oracle Turing machine)
26.More uncomputable problems
We are in a similar situation as in the theory of NP-completeness
We have an uncomputable/undecidable problem, find more by reductions
27.Example
H={: M halts on some input x2{0,1}*}
Theorem: H is not computable because HALT· H
Reduction: given ,x we construct a new TM Mx
Mx ignores its own input but writes x on the tape and then simulates M on x
Clearly: ,x2 HALT , 2 H
Note: The description of has to be computable from and x
28.Example
LM denotes the language accepted by M
the set of strings that M accepts
NEMPTY={: LM ;}
Theorem: E is not decidable because HALT· NEMPTY
Reduction:
Given ,x we create a new machine Mx
Mx reads the input and compares it to x
If input is not equal to x, then Mx rejects
If input is equal to x, then Mx simulates M
If M halts, accept
We have: ,x2 HALT , 2 NEMPTY