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!