1
$\begingroup$

In the definition of the complexity class $\mathcal {NP}$; Why does one require the existence of an algorithm $\mathcal A$, such that

  • for each instance $I$ of the problem, there exists a solution $x_0\in Sol(I)$ such that $\mathcal A$ accepts $(I,x_0)$ in polynomial time

rather than

  • for each instance of the problem and each solution $x_0\in Sol(I)$, $\mathcal A$ accepts $(I,x_0)$ polynomial time

I ask this, because I was told that $\mathcal{NP}$ tries to capture the idea that some problems are hard to solve, but easy to check. And the second definition - it seems naively - would be the right one for this.

  • What is the reason for not requiring the algorithm to accept every solution to a given instance of the problem?

The only problem with the 2nd version that I could see is that $x_0$ may not be bounded in size polynomially in $|I|$ (so reading it might already take too long). What if one adds a requirement to prevent such a thing?

Thanks for your help!

1 Answers 1

2

The word "solution" is rather confusing here. Instead, try this:

for each instance $I$ of the problem, there exists a string $s$ such that $\mathcal A$ accepts $(I,s)$.

Then, we can call such strings $s$ "solutions". So $I$ is an instance iff there exists a solution for $I$.

The algorithm accepts each solution, but this remark is content-less, because that's how we defined: a solution is something that is accepted by the algorithm.

As for bounds, in this definition both $s$ must have length polynomial in length of $I$, and $\mathcal A$ must be a polynomial time algorithm. Since time is measured relatively to input size, and input to $\mathcal A$ is $(I,s)$, if you allowed $s$ to be long, $\mathcal A$ could perform very long computation.

  • 0
    Hmm, then I'm not sure I've understood the definitions. It says here in my script: A decision problem $\Pi$ is a tuple $\langle \mathcal I, Sol\rangle$, which consists of a set of problem instances $\mathcal I \subset \Sigma^\ast$ and for each instance $I\in \mathcal I$, the set $Sol(I)\subset \Sigma^\ast$ denotes the set of solutions to $I$. Here $\Sigma$ is an alphabet and $\Sigma^\ast$ are all words over this alphabet. So, from this I would think that the term "solution" is independent of $\mathcal A$ (Note: Definitions translated from German - so terminology might differ from standard one)2012-01-02
  • 0
    So couldn't then there be an algorithm $\mathcal A$, which accepts $(I,s_I)$ for exactly one $s_I\in Sol(I)$ to each instance $I$, but rejects all other $(I,s)$ (even though there may be many actual solution to the problem among them)? This would then mean, that we'd have to be extremely lucky to pick out the right $s$ amongst $Sol(I)$ for the algorithm to accept it. So, in practice, the problem might not be easy to check at all! Where am I wrong?2012-01-02
  • 0
    Hm, this is very peculiar, I never saw "decision problem" defined in that way. In standard textbooks, decision problems are defined as subsets of $\Sigma^{\ast}$. Anyway, I suggest you read the definition in the following way: the algorithm has to accept $(I,s_I)$ iff $s_I$ is a solution for $I$, and $I$ is in a language (i.e. has answer "yes") iff there exists a solution for it.2012-01-02
  • 0
    I have now read through the relevant sections of *Introduction to Algorithms* by T. Cormen, C. Leiserson, R. Rivest, C. Stein. It indeed seems that the definition there does not quite agree with the one given in my script (what they call a 'concrete problem' is what my script calls a "Entscheidungsproblem", i.e. decision problem). But a 'decision problem' seems to be a term usually reserved for a problem with solution set $Sol = \{0,1\}$ and such that for each $x \in \mathcal I$ either $(x,0)\in \Pi$ or $(x,1)\in \Pi$ (but not both). (cont)2012-01-02
  • 0
    ... So that the problem $\Pi = \langle \mathcal I, Sol\rangle$ in this case can be identified with the language $$L = \{x\in \Sigma^\ast\mid (x,1)\in \Pi\}$$2012-01-02
  • 0
    I will have to think about the connections between the definitions of $\mathcal{NP}$ given there and in my script. They don't seem to agree either.2012-01-02
  • 0
    Sam: Yes. Decision problems have either "yes" or "no" answers and are identified with the set of "yes" instances. [Search problems](http://en.wikipedia.org/wiki/Search_problem) correspond to relations. NP is a class of decision problems. There is a functional version of NP - FNP class, and perhaps the script (very confusingly) refers to it. Beware, "[Entscheidungsproblem](http://en.wikipedia.org/wiki/Entscheidungsproblem)" has another meaning, namely it refers to unsolvability of halting problem.2012-01-02
  • 0
    Thank you very much for the feed-back. I think you may be right about the FNP class. This is the class of all problems for which the corresponding decision problem is in NP, right? So for a given instance $I\in \mathcal I$, the decision problem asks: "$Sol(I) \ne \emptyset$?" and a certificate $y$ for $I$ would be some $y\in Sol(I)$. So that the algorithm $\mathcal A$ would check (in polynomial time in $|I|$), whether $y \in Sol(I)$. This seems to make sense.2012-01-02
  • 0
    Sam: Yes, this is true, if $(x,y) \in R$ can be decided in polynomial time, then the decision problem whether such $y$ exists given some $x$ is in NP. Looking back at the original question, your doubts about what is the relation between $\mathcal A$ and $Sol(I)$ are justified. I think it's better to require that $\mathcal A$ accepts exactly the set $\{(I,y): y \in Sol(I)\}$.2012-01-02
  • 0
    O.k. I have now read on in the script, and later on they state in a proof: "Let $\Pi = \langle \mathcal I, Sol\rangle$ be an arbitrary problem in NP, and let $\mathcal A$ be a polynomial-time algorithm, which decides for each pair $I\in \mathcal I$ and $x \in \Sigma^\ast$, whether $x\in Sol(I)$..." So it might be that they've tried to avoid technicalities best as possible (i.e. avoiding formal-language theory) and then simply have stated a slightly wrong/bad definition. The course is more of an overview anyways. Thanks again. =)2012-01-02