Lecture 24 (The classes P and NP), 4/19/06

Concepts, definitions (in italics):

• Time complexity of TM computations -- number of transitions
• Time complexity is a function of size of input (length of input string).
• Worst-case vs. average-case complexity -- worst case is default
• TIME(f(n)) -- set (class) of languages decidable by a standard (1-tape, deterministic) TM with O(f(n)) time complexity
• Time complexity depends on the model of computation used; the class TIME assumes that standard TM is the model of computation.
• P is a set of languages; P = U TIME(n^k) =  TIME(n) U TIME(n²) U TIME(n³) U ...
• P corresponds to tractable problems (realistically solvable by computers)
• Polynomial equivalence of standard TMs, multitape TMs, and RAM algorithms -- if there exists a P-time random access or multitape (deterministic) algorithm, then same algorithm can be done in P-time on a standard TM
• P is robust
• Nondeterministic time complexity: time complexity for non-deterministic TM (corresponds to algorithms where "coin flips" are allowed)
• A nondeterministic TM M decides L in non-deterministic polynomial time if:
  • for all x, the computational tree of M on x has polynomial depth
  • if x is in L, there exists an accepting computation of M on x
  • if x is not in L, an accepting computation does not exist
• NTIME, NP
• P is a subset of NP (all problems in P are automatically in NP)
• It is an open question whether P = NP (determinism vs. non-determinism)
• Venn Diagrams of 2 possible worlds: (1) P = NP or (2) there exists some "magic" L in NP that's not in P

Reading:

• Chapter 7.1
• Chapter 7.2 to middle of p. 258 (examples of problems)

Skills:

• Know new definitions, understand new concepts
• Find the time complexity of a given TM.
• Given a decidable language, how to you show it is in P -- find a standard or a multitape TM, or a RAM algorithm, that decides it in polynomial time.
• Given a decidable language, how to you show it is in NP?
• Understand why P is a subset of NP

Notes:

• The problem L we saw today is in TIME(n²) and in TIME(n log n) but not in TIME(n).