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.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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) –  Sam Jan 2 '12 at 8:19
    
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? –  Sam Jan 2 '12 at 8:24
    
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. –  sdcvvc Jan 2 '12 at 8:35
    
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) –  Sam Jan 2 '12 at 10:02
    
... 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\}$$ –  Sam Jan 2 '12 at 10:02

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.