Two Variants of NP

Question

Here are two variations on the definition of NP. They (almost certainly) define distinct complexity classes, but my question is: are there natural examples of problems that fit into these classes?

(My threshold for what counts as natural here is a bit lower than usual.)

Class 1 (a superclass of NP): Problems with polynomial-size witnesses that take superpolynomial but subexponential time to verify. For concreteness, let's say time $n^{O(\log n)}$. This is equivalent to the class of languages recognized by nondeterministic machines that take time $n^{O(\log n)}$ but can only make poly(n) nondeterministic guesses.

Are there natural problems in class 1 that is not known/thought to be either in $NP$ nor in $DTIME(n^{O(\log n)})$?

Class 1 is a class of languages, as usual. Class 2, on the other hand, is a class of relational problems:

Class 2: A binary relation R = {(x,y)} is in this class if

1. There is a polynomial p such that (x,y) in R implies |y| is at most p(|x|).
2. There is a poly(|x|)-time algorithm A such that, for all inputs x, if there is a y such that (x,y) is in R, then (x,A(x)) is in R, and if there is no such y, then A(x) rejects.
3. For any poly(|x|)-time algorithm B, there are infinitely many pairs (x,w) such that B(x,w) differs from R(x,w) (here I am using R to denote its own characteristic function).

In other words, for all instances, some witness is easy to find if there is one. And yet not all witnesses are easily verifiable.

(Note that if R is in class 2, then the projection of R onto its first factor is simply in P. This is what I meant by saying that class 2 is a class of relational problems.)

Are there natural relational problems in class 2?

Answer 1

For Class 2, one somewhat silly example is

R(p, a) = {p is an integer polynomial, a is in the range of p, and |a| = O(poly(|p|)}.

R is in Class 2 but undecidable.

Answer 2

I would request that you clarify the witness condition in class 1 a bit. It seems that any appropriately bounded problem from co-NP would seem to do the trick, is this what you intended?

For example, take the class of all graphs that do not have a clique of size $\log n$. The witness, of course, is the graph itself, and performing this check is (I believe) not believed to be possible in polynomial time. (See for example the parameterized complexity status of the problem, and the results of Chen et al. here.)

Answer 3

This isn't an example of a natural problem, but a family of problems in Class 1, but probably not in NP or QP = DTIME(n^{polylog n}). Perhaps someone here can instantiate the function $f$ and get a concrete problem out.

Let $f(x_1,x_2,\ldots, x_n,y_1,y_2,\ldots,y_m)$ be a polynomial time computable predicate, with m = polylog n.

The problem $\exists x \forall y f(x_1,x_2,\ldots, x_n,y_1,y_2,\ldots,y_m)$ is in your class 1.

It's probably not in QP because it can express all problems in NP, and it's probably not in NP because it can express all problems in co-NTIME(polylog).