Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I understand that NP describes the class of problems to which the solutions can be verified in polynomial time, but I have trouble understanding its definition. The below is my book's definition:

We say that B is an efficient certifier for a problem X if the following properties hold.

  • B is a polynomial-time algorithm that takes two input arguments $s$ (the input string) and $t$ (a certificate string).

  • There is a polynomial function $p$ so that for every string $s$, we have $s \in X$ if and only if there exists a string $t$ such that $|t| \le p(|s|)$ and $B(s,t)=yes$.

We define NP to be the set of all problems for which there exists an efficient certifier.

questions:

  1. Is $s$ the problem and $t$ its solution? If so, then what is the difference between $s$ and $X$?

  2. What is $p(|s|)$? What does $|t| \le p(|s|)$ mean? How does this fit in the definition?

Thanks in advance!

share|improve this question
1  
$s$ is an instance of a problem $X$ and $t$ is the solution. For example, $[28, 3, 8, 22, 9, 11, 6, 21, 24, 8]$ (properly encoded) could be $s$ and $(+1, +1, -1, +1, +1, -1 -1, -1, -1, +1)$ could be $t$ (i.e. 28 +3 -8 +22 +9 -11 -6 -21 -24 +8 = 0 ). $X$ in this case is a class of problems from which you can can test inclusion of given an instance and solution to. –  user4143 Apr 11 '11 at 9:23

1 Answer 1

up vote 3 down vote accepted

Question 1: This is resolved by precise use of the word "problem". You seem to be using it in a different way from how your book defines it (and how it's usually defined). $s$ is a problem instance. For example, the traveling salesman problem isn't just one set of distances, but the entire class of problem instances, where each particlar problem instance is specified by a particular set of distances. So $s$ is a string specifying a particular instance of the problem $X$.

Question 2: $|s|$ is the length of the string $|s|$ and $p$ is a polynomial function, so $p(|s|)$ is just that polynomial function applied to the length of $s$. Similarly, $|t| \le p(|s|)$ means that the length of the string $t$ is bounded by the polynomial function $p$ of the length of the string $s$. In other words, the length of the description of the certificate is at most polynomial in the length of the description of the problem instance.

[Edit in response to the comment:] Going through your additional questions one by one:

"But how are the amount of work done by B based on the size of those strings?" I don't understand that question; it's ungrammatical.

"I see time complexity as something based on a problem's input size, but I have trouble seeing the size of those strings as the input size." What does "those strings" refer to here?

"Another question: In the "s∈X iff..." statement, is the X here refering to a NP problem?" At that point it isn't, since that statement is in the definition of an efficient verifier and there's no talk about NP yet. But the subsequent definition of NP in terms of efficient verifiers means that if there is such a $B$, then $X$ is by definition an NP problem.

"Why does B(s,t) have to be yes? Is a problem considered NP if a solution can be verified to be false in polynomial time?" The term "solution" isn't used in the definition, but I'm guessing that you might mean something like this: Consider the decision version of the traveling salesman problem, i.e. "Is there a tour of length $<L$?", so $X$ is the set of instances in which there is such a tour. Then a certificate string is a description of a tour, and I presume by a "false solution" you mean a certificate string describing a tour of length $\ge L$, i.e. one that doesn't certify that the instance is in $X$.

$B$ is a polynomial-time algorithm. The definition doesn't say that it runs in polynomial time only if the result is "yes"; it always runs in polynomial time. In particular, it runs in polynomial time and answers "no" (or anything else other than "yes") if you feed it a "false solution".

You're right more generally, however, in noticing that there's an asymmetry here. But the asymmetry is not in the ability to check certificates, but in their existence. Whereas NP is defined as the class of problems for which there exists a (polynomial-time-verifiable) "yes" certificate for all "yes" instances, co-NP is defined as the class of problems for which there exists a (polynomial-time-verifiable) "no" certificate for all "no" instances. In the case of the decision version of TSP, such a "no" certificate would not be a "false solution" in the sense of a tour with length $\ge L$ (which proves nothing either way), but a (polynomial-time-verifiable) proof that no tour of length $<L$ exists. While there are of course proofs for all "no" instances that no such tour exists (namely calculations of the lengths of all tours), their length is not polynomial in the problem size, and hence they can't be verified in polynomial time. If, in analogy to your definition, there were an algorithm B(s,t) such that $s\notin X$ if and only if there exists a string $t$ such that $|t|\le p(|s|)$ and $B(s,t)=$"no", i.e. if there were polynomial-time-verifiable proofs for all "no" instances that they are "no" instances, then the problem would be in co-NP. No such (polynomial-time-verifiable) proofs are known for TSP, and hence it is not known to be in co-NP. If there were such proofs, it would follow that co-NP=NP, which is believed not to be the case; see the Wikipedia article on co-NP.

share|improve this answer
    
thanks for the reply! So here is my understanding: $s$ is a string representation of an instance of a problem, and $t$ is that of its solution. But how are the amount of work done by $B$ based on the size of those strings? I see time complexity as something based on a problem's input size, but I have trouble seeing the size of those strings as the input size. Another question: In the "$s \in X$ iff..." statement, is the $X$ here refering to a NP problem? Why does $B(s,t)$ have to be yes? Is a problem considered NP if a solution can be verified to be false in polynomial time? thanks :) –  user8969 Apr 12 '11 at 1:02
    
@mathcat: I edited the answer in response to your further questions. –  joriki Apr 12 '11 at 11:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.