Lecture 25 (The class VP), 4/24/06

Concepts, definitions (in italics):

• The languages (problems) PATH, HAMPATH, RELPRIME, PRIMES, COMPOSITE
• A (polynomial-time) verifier for a language L
• L is (polynomial-time) verifiable if there exists a (polynomial-time) verifier for it
• The class VP of polynomially verifiable problems/languages
• HAMPATH, COMPOSITE are in VP
• Theorem 7.17 a language is decideable in non-deterministic polynomial time iff it is polynomially verifiable (NP = VP)
• Corollary: It is an open question whether P = VP (computability vs. verifiability) 

Reading:

• Chapter 7.3

Skills:

• Know new definitions, understand new concepts
• What is a hamiltonian path in G?
• What if a verifier is given w that's not in L? (then it will reject w, no matter what the certificate is)

Notes:

• Certificate for x in L (a string) = "proof" that x belongs to L 
• Note: the book defines NP as we define VP (defn. 7.19), but it proves right away that the two sets are the same (theorem 7.20).
• If A is in P then its complement is also in P (P is closed under complement)
• A mapping reduction from L1 to L2 is the same as a mapping reduction from the complement of L1 to the complement of L2
• The problems PATH, RELPRIME, A (ch. 7) are in P; PRIMES is not known to be in P
• Euclid's Algorithm - for finding largest common factor, discovered in ancient Greece.