Understanding Computational Complexity Theory: Diagonalization, Time Hierarchy, Ladner's Theorem

computational complexity theory n.w
1 / 73
Embed
Share

Dive into the world of computational complexity theory with a focus on important concepts like diagonalization, time hierarchy, and Ladner's theorem. Explore the workings of nondeterministic Turing machines, NP, decision versus search, and more at the Indian Institute of Science.

  • Complexity Theory
  • Diagonalization
  • Time Hierarchy
  • Ladners Theorem
  • NP
rayaanacharya
simo_ean Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Computational Complexity Theory Lecture 5: Diagonalization,Time Hierarchy, Ladner s theorem Indian Institute of Science

  2. Recap: NTMs A nondeterministic Turing machine is like a deterministic Turing machines but with two transition functions. It is formally defined by a tuple ( , Q, 0 , 1). It has a special state qaccept in addition to qstart and qhalt. At every step of computation, the machine applies one of two functions 0 and 1arbitrarily. Unlike DTMs, NTMs are not intended to be physically realizable (because of the arbitrary nature of application of the transition functions).

  3. Recap: NTMs Definition. An NTM M accepts a string x {0,1}* iff on input x there exists a sequence of applications of the transition functions 0 and 1 (beginning from the start configuration) that makes M reach qaccept. Defintion. An NTM M decides a language L {0,1}* if M accepts x x L On every sequence of applications of the transition functions on input x, M either reaches qaccept or qhalt.

  4. Recap: NTMs Definition. An NTM M accepts a string x {0,1}* iff on input x there exists a sequence of applications of the transition functions 0 and 1 (beginning from the start configuration) that makes M reach qaccept. Defintion. An NTM M decides L in T(|x|) time if M accepts x x L On every sequence of applications of the transition functions on input x, M either reaches qaccept or qhalt within T(|x|) steps of computation.

  5. Recap: Another definition of NP Definition. A language L is in NTIME(T(n)) if there s an NTM M that decides L in c. T(n) time on inputs of length n, where c is a constant. Theorem. NP = NTIME (nc). c > 0

  6. Recap: Decision versus Search Recall: A language L {0,1}* is in NP if There s a poly-time verifier M such that x L iff there s a poly-size certificate u s.t M(x,u) = 1 Search version of L: Given an input x {0,1}*, find a u {0,1}p(|x|) such that M(x,u) = 1, if such a u exists. Example: Given a 3CNF , find a satisfying assignment for if such an assignment exists.

  7. Recap: Decision versus Search Is the search version of an NP-problem more difficult than the corresponding decision version? Theorem. Let L {0,1}* be NP-complete. Then, the search version of L can be solved in poly-time if and only if the decision version can be solved in poly-time. Theorem. (Bellare-Goldwasser) If EE NEE then there s a language in NP for which search does not reduce to decision.

  8. Recap: Class co-NP Definition. For every L {0,1}* let L = {0,1}* \ L. A language L is in co-NP if L is in NP. Another definition. A language L {0,1}* is in co-NP if there s a poly-time TM M such that x L u {0,1}p(|x|) s.t. M(x, u) = 1 NP co-NP P

  9. Recap: Class EXP Definition. Class EXP is the exponential time analogue of class P. EXP = DTIME ( 2n ) c 1 c Observation. P NP EXP EXP NP co-NP P

  10. Recap: Class EXP Definition. Class EXP is the exponential time analogue of class P. EXP = DTIME ( 2n ) c 1 c Observation. P NP EXP Exponential Time Hypothesis. (Impagliazzo & Paturi) Any algorithm for 3-SAT takes time (2 .n), where is a constant and n is the input size.

  11. Diagonalization

  12. Diagonalization Diagonalization refers to a class of techniques used in complexity theory to separate complexity classes.

  13. Diagonalization Diagonalization refers to a class of techniques used in complexity theory to separate complexity classes. These techniques are characterized by two main features:

  14. Diagonalization Diagonalization refers to a class of techniques used in complexity theory to separate complexity classes. These techniques are characterized by two main features: 1. There s a universal TM U that when given strings and x, simulates M on x with only a small overhead.

  15. Diagonalization Diagonalization refers to a class of techniques used in complexity theory to separate complexity classes. These techniques are characterized by two main features: 1. There s a universal TM U that when given strings and x, simulates M on x with only a small overhead. If M takes T time on x then U takes O(T log T) time to simulate M on x.

  16. Diagonalization Diagonalization refers to a class of techniques used in complexity theory to separate complexity classes. These techniques are characterized by two main features: 1. There s a universal TM U that when given strings and x, simulates M on x with only a small overhead. 2. Every string represents some TM, and every TM can be represented by infinitely many strings.

  17. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). e.g. f(n) = n, g(n) = n2

  18. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n))

  19. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2.

  20. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. Task: Show that there s a language L decided by a TM D with time complexity O(n2) s.t., any TM M with runtime O(n) cannot decide L.

  21. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. TM D : 1. On input x, compute |x|2.

  22. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. TM D : 1. On input x, compute |x|2. 2. Simulate Mx on x for |x|2 steps.

  23. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. TM D : 1. On input x, compute |x|2. 2. Simulate Mx on x for |x|2 steps. a. If Mx stops and outputs b then output 1-b

  24. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. TM D : 1. On input x, compute |x|2. 2. Simulate Mx on x for |x|2 steps. a. If Mx stops and outputs b then output 1-b b. otherwise, output 1.

  25. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. D runs in O(n2) time as n2 is time-constructible.

  26. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. Claim. There s no TM M with running time O(n) that decides L (the language accepted by D).

  27. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n.

  28. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. c is a constant

  29. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. Think of a sufficiently large x such that M = Mx

  30. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. Think of a sufficiently large x such that M = Mx Suppose Mx(x) = b

  31. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. Think of a sufficiently large x such that M = Mx Suppose Mx(x) = b D on input x, simulates Mx on x for |x|2 steps.

  32. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. Think of a sufficiently large x such that M = Mx Suppose Mx(x) = b D on input x, simulates Mx on x for |x|2 steps. Since Mx stops within c.|x| steps, D s simulation also stops within c .c. |x|. log |x| steps.

  33. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. Think of a sufficiently large x such that M = Mx Suppose Mx(x) = b D on input x, simulates Mx on x for |x|2 steps. Since Mx stops within c.|x| steps, D s simulation also stops within c .c. |x|. log |x| steps. c is a constant

  34. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. Think of a sufficiently large x such that M = Mx Suppose Mx(x) = b D on input x, simulates Mx on x for |x|2 steps. Since Mx stops within c.|x| steps, D s simulation also stops within c .c. |x|. log |x| steps. (as c .c. |x|. log |x| < |x|2 for sufficiently large x)

  35. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. Think of a sufficiently large x such that M = Mx Suppose Mx(x) = b D on input x, simulates Mx on x for |x|2 steps. Since Mx stops within c.|x| steps, D s simulation also stops within c .c. |x|. log |x| steps. And D outputs the opposite of what Mx outputs.

  36. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. Think of a sufficiently large x such that M = Mx Suppose Mx(x) = b Hence, D(x) = 1-b

  37. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Proof. We ll prove with f(n) = n and g(n) = n2. For contradiction, suppose M decides L and runs for at most c.n steps on inputs of length n. Think of a sufficiently large x such that M = Mx Suppose Mx(x) = b Hence, D(x) = 1-b Contradiction! M does not decide L.

  38. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Theorem. P EXP

  39. Time Hierarchy Theorem Let f(n) and g(n) be time-constructible functions s.t., f(n) . log f(n) = o(g(n)). Theorem. DTIME(f(n)) DTIME(g(n)) Theorem. P EXP Proof. Similar (homework)

  40. NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete.

  41. NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. NPC NP-intermediate NP P

  42. NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. the notion makes sense only if P NP

  43. NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language.

  44. NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language. Proof. A delicate argument using diagonalization.

  45. NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language. Proof. Let H: N N be a function.

  46. NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language. Proof. Let H: N N be a function. Let SATH = { 0 1 : SAT and | | = m} mH(m)

  47. NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. Theorem. (Ladner) If P NP then there is an NP- intermediate language. Proof. Let H: N N be a function. Let SATH = { 0 1 : SAT and | | = m} mH(m) H would be defined in such a way that SATH is NP-intermediate (assuming P NP )

  48. Ladners theorem: Constructing H Theorem. There s a function H: N N such that 1. H(m) is computable from m in O(m3) time

  49. Ladners theorem: Constructing H Theorem. There s a function H: N N such that 1. H(m) is computable from m in O(m3) time 2. SATH P H(m) C (a constant) for every m

  50. Ladners theorem: Constructing H Theorem. There s a function H: N N such that 1. H(m) is computable from m in O(m3) time 2. SATH P H(m) C (a constant) 3. If SATH P then H(m) with m

Related


No related presentations.

More Related Content