Ladner's Theorem in Computational Complexity Theory

Ladner's Theorem is a significant result in computational complexity theory that deals with NP-intermediate problems, which are languages in NP neither in P nor NP-complete. The theorem states that if P is not equal to NP, then there must exist an NP-intermediate language. The proof involves a delicate argument using diagonalization techniques.

• Ladners Theorem
• Computational Complexity
• NP-intermediate
• Diagonalization

gatz_waz Follow

Uploaded on Sep 12, 2024 | 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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Computational Complexity Theory Lecture 6: Ladner s theorem Indian Institute of Science

2. Recap: 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.

3. Recap: 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

4. Ladners Theorem - Another application of Diagonalization

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

6. 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

7. NP-intermediate problems Definition. A language L in NP is NP-intermediate if L is neither in P nor NP-complete. NPC NP-intermediate (integer factoring, graph isomorphism ??) NP P

8. 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

9. 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.

10. 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.

11. 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.

12. 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)

13. 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 )

14. 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

15. 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

16. 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

17. 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 Proof: Later (uses diagonalization).

18. Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C.

19. Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows:

20. Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |.

21. Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |. mH(m) Compute H(m), and construct the string 0 1

22. Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |. mH(m) Compute H(m), and construct the string 0 1 mH(m) Check if 0 1 belongs to SATH

23. Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |. mH(m) Compute H(m), and construct the string 0 1 mH(m) Check if 0 1 belongs to SATH length at most m + 1 + mC

24. Ladners theorem: Proof P NP Suppose SATH P. Then H(m) C. This implies a poly-time algorithm for SAT as follows: On input , find m = | |. mH(m) Compute H(m), and construct the string 0 1 mH(m) Check if 0 1 belongs to SATH As P NP, it must be that SATH P .

25. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m.

26. Ladners theorem: Proof P NP This also implies a poly-time algorithm for SAT: Suppose SATH is NP-complete. Then H(m) with m. f 0 1k SAT p SATH

27. Ladners theorem: Proof P NP This also implies a poly-time algorithm for SAT: Suppose SATH is NP-complete. Then H(m) with m. f 0 1k SAT p SATH | | = n | 0 1k| = nc

28. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |.

29. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m).

30. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Either m is small (in which case the task reduces to checking if a small is satisfiable),

31. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). or H(m) > 2c (as H(m) tends to infinity with m).

32. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, w.lo.g. |f( )| m2c

33. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, w.l.o.g. nc = |f( )| m2c

34. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m

35. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m. Also SAT iff SAT

36. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m. Also SAT iff SAT Thus, checking if an n-size formula is satisfiable reduces to checking if a n-size formula is satisfiable.

37. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m. Also SAT iff SAT Do this recursively! Only O(log log n) recursive steps required.

38. Ladners theorem: Proof P NP Suppose SATH is NP-complete. Then H(m) with m. This also implies a poly-time algorithm for SAT: f 0 1k SAT p SATH On input , compute f( ) = 0 1k. Let m = | |. Compute H(m) and check if k = mH(m). Hence, n m. Also SAT iff SAT Hence SATH is not NP-complete, as P NP.

39. Ladners theorem: Properties of 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 mH(m) SATH = { 0 1 : SAT and | | = m}

40. Construction of H Observation. The value of H(m) determines membership in SATH of strings whose length is m. Therefore, it is OK to define H(m) based on strings in SATH whose length is < m (say, log m).

41. Construction of H Observation. The value of H(m) determines membership in SATH of strings whose length is m. Therefore, it is OK to define H(m) based on strings in SATH whose length is < m (say, log m). Construction. H(m) is the smallest k < log log m s.t. 1. Mk decides membership of all length up to log m strings x in SATH within k.|x|k time. 2. If no such k exists then H(m) = log log m.

42. Construction of H Observation. The value of H(m) determines membership in SATH of strings whose length is m. Therefore, it is OK to define H(m) based on strings in SATH whose length is < m (say, log m). Homework. Prove that H(m) is computable from m in O(m3) time.

43. Construction of H Claim. If SATH P then H(m) C (a constant). Proof. There is a poly-time M that decides membership of every x in SATH within c.|x|c time.

44. Construction of H Claim. If SATH P then H(m) C (a constant). Proof. There is a poly-time M that decides membership of every x in SATH within c.|x|c time. As M can be represented by infinitely many strings, there s an c s.t. M = M decides membership of every x in SATH within .|x| time. So, for every m satisfying < log log m, H(m) .

45. Construction of H Claim. If H(m) C (a constant) then SATH P. Proof. There s a k C s.t. H(m) = k for infinitely many m.

46. Construction of H Claim. If H(m) C (a constant) then SATH P. Proof. There s a k C s.t. H(m) = k for infinitely many m. Pick any x {0,1}*. Think of a large enough m s.t. |x| log m and H(m) = k.

47. Construction of H Claim. If H(m) C (a constant) then SATH P. Proof. There s a k C s.t. H(m) = k for infinitely many m. Pick any x {0,1}*. Think of a large enough m s.t. |x| log m and H(m) = k. This means x is correctly decided by Mk in k.|x|k time. So, Mk is a poly-time machine deciding SATH.

48. Natural NP-intermediate problem? Integer factoring. FACT = {(N, U): there s a prime U dividing N} Claim. FACT NP co-NP So, FACT is NP-complete if and only if NP = co-NP.