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
    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