1
$\begingroup$

We define $\mathbf P$ as the set of problems solvable in polynomial time. We define $\mathbf{NP}$ as the set of problems with a verifier $ \in \mathbf P$.

Is there a name for problems whose verifiers are $\in \mathbf {NP}$ (e.g., $\mathbf{N(NP)}$)? I can't see this being a very useful complexity class, but, for example we have that $\mathbf{NP} \neq \mathbf{N(NP)} \implies \mathbf{P} \neq \mathbf{NP}$, so it might be an area of research for that reason alone.

$\endgroup$
  • $\begingroup$ Why do you think that NP≠N(NP) implies P≠NP? $\endgroup$ – David Richerby May 2 '17 at 19:17
  • $\begingroup$ P = NP -> NP = N(NP), so by the contrapositive. $\endgroup$ – k_g May 2 '17 at 21:33
3
$\begingroup$

Suppose you had a problem such that for any $x \in L$, there was a verifier $v$ such that $v$ could be checked against $x$ by a nondeterministic polynomial time algorithm. For a valid $(x, v)$ pair, there is some verifier $v'$ such that it takes polynomial time to check $((x, v), v')$ is a correct verification.

But then, you could simply combine $(v, v')$ into a single witness, and run the check in deterministic polynomial time.

Thus, the class ${\bf N(NP)}$ you describe is really just equal to ${\bf NP}$.

$\endgroup$
0
$\begingroup$

If a problem has a verifier you can guess it with nondeterministic TM so it is automatically in NP.

$\endgroup$
  • 1
    $\begingroup$ You need more detail, here. If the verifier has exponential witnesses or requires exponential time on a nondeterministic Turing machine, you've not established membership in NP. The verifier in the question is not the standard one. $\endgroup$ – David Richerby May 2 '17 at 19:13
  • $\begingroup$ Agree, I put a thought in words and it became to sound more generally. Here we have a nondeterministic TM with polynomial time for everything. Might be not true if we have another witnesses. Good point! $\endgroup$ – Eugene May 2 '17 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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