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$
2
  • $\begingroup$ Why do you think that NP≠N(NP) implies P≠NP? $\endgroup$ Commented May 2, 2017 at 19:17
  • $\begingroup$ P = NP -> NP = N(NP), so by the contrapositive. $\endgroup$
    – k_g
    Commented May 2, 2017 at 21:33

2 Answers 2

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
0
$\begingroup$

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

$\endgroup$
2
  • 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$ Commented May 2, 2017 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
    Commented May 2, 2017 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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