# Decision problems whose verifier is NP

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.

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

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}$.

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

• 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. – David Richerby May 2 '17 at 19:13
• 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! – Eugene May 2 '17 at 19:40