CSC 341: April 30, 2007

From CSWiki

1 Instructor's notes for the class session
- 1.1 Polynomial verifiability
- 1.2 NP-completeness
2 Study questions

Instructor's notes for the class session

Polynomial verifiability

A verifier for a language is a Turing machine that decides the language with the help of an extra input, which can be any string (and can be different for different members of the language). A language is polynomially verifiable if some verifier for it has a running-time function that is $O (n k)$ for some positive integer $k$ . (In this definition, $n$ is the length of the candidate for language membership and does not include the extra input.)

Definition 7.19: NP is the class of polynomially verifiable languages.

Theorem 7:20: A language is polynomially verifiable if, and only if, it is decided by a nondeterministic Turing machine with a running-time function that is math>O(n^k)</math> for some positive integer $k$ . The proof is that a polynomial-time verifier can be simulated by a polynomial-time nondeterministic Turing machine (it guesses the extra input) and vice versa (a trace of the nondeterministic Turing machine's choices can be used as the extra input).

Examples of polynomially verifiable languages: $H A M P A T H$ , $C O M P O S I T E S$ , $C L I Q U E$ , $S U B S E T - S U M$ , $S A T$ , $3 S A T$ .

Typically, we prove that a language is polynomially verifiable by constructing either a polynomial-time verifier for it or a polynomial-time nondeterministic Turing machine that decides it.

It is not known whether $P = NP$ , but most experts on algorithms and computational complexity incline to the view that this proposition is false, since so many people have tried uncessfully to design polynomial-time algorithms for problems that are known to be in NP but not known to be in P.

[edit]

NP-completeness

Definition 7.28: A language $A$ is polynomial time reducible to a language $B$ if there is a polynomial time computible function that maps members of $A$ to members of $B$ and non-members of $A$ to non-members of $B$ .

Theorem 7.31: If $A \le_{\mathrm{P}} B$ and $B \in \mathrm{P}$ , then $A \in \mathrm{P}$ . The proof centers around the fact that the composition of two functions with polynomial running times itself has a polynomial running time.

Definition: A language is NP-hard if, and only if, every polynomially verifiable language is polynomial time reducible to it.

Definition 7.34: A language is NP-complete if, and only if, it is both polynomially verifiable and NP-hard.

Theorem 7.35: If any member of P is NP-complete, then $P = NP$ .

Theorem 7.36: If an NP-complete language $B$ is polynomial time reducible to a member $C$ of NP, then $C$ is NP-complete.

[edit]

Study questions

Show that there is a polynomial-time verifier for the problem of testing whether two given regular expressions correspond to the same language.
Consider the Bounded Post Correspondence Problem: In addition to specifying the set of dominoes, we specify, as a parameter of the problem, an upper bound on the length of valid solutions to the problem. (Domino sequences of lengths exceeding the upper bound are disqualified, even if the concatenations of their tops and bottoms match up correctly.) Show that $\textit{BPCP} \in \textrm{NP}$ .
Why can't the solution to the preceding study question be adapted to prove that $\textit{PCP} \in \textrm{NP}$ ?.

Proposed Solutions:

To show that the $B P C P$ is in $NP$ , it will suffice to construct a polynomial-time verifier for the $B P C P$ . Let this machine be called $M$ . $M$ will run on the encoding of the proposed solution, $S$ , and the upper bound of the solution, $n$ . $M$ must first verify that $S$ does not exceed the upper bound on length, in no more than $n$ steps. Next, M verifies that the top string in $S$ matches with the bottom string in $S$ . This can be accomplished by writing each string onto $M$ 's tape, and then shuttling back and forth between each corresponding character in some constant times $n$ steps. As $M$ verifies the $B P C P$ in polynomial time, $\textit{BPCP} \in \textrm{NP}$ .
Since the $P C P$ does not have an upper bound, a verifier must traverse an unknown distance to check that both strings in a proposed solution match, so in turn running time is not bounded by $n$ as it was in the above solution.