Download

Algorithms (and Datastructures) - Theory of Computing, MAS 714 Hartmut Klauck, Subset Sum, Input: set S of natural numbers

Upload
0
Embed
Share
Upload and view presentations on any device and embed the player to your website! --- > >
Upload PPT
Upload PPT

Download this Presentation

asdas4sds54

2021-9-26 published at Celebrities category

Presentation Transcript

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

Latest Release