2
$\begingroup$

Define the class $X$ of languages by the condition that a language $L$ over alphabet $\Sigma$ is in $X$ iff there are a constant $c > 0$ and a polynomial-time checking relation $R$ such that for all $w \in \Sigma^*$,

$$w \in L \Leftrightarrow \exists y \in \Sigma^*.\ |y| \leq c|w| \text{ and } R(w, y)$$ where $|w|$ and $|y|$ denote the lengths of $w$ and $y$, respectively.

Of course this is a modification of the verifier-based definition of NP obtained replacing the polynomial bound on the size of certificates with a linear bound. Has this class been studied? Is it just P ?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Well it’s clearly not P (assuming P $\ne$ NP), as every NP language reduces to a language in this class. This follows either by a trivial padding argument, or by observing that pretty much all standard NP-complete languages are in this class: SAT, 3-Colourability, Hamiltonian path, you name it. $\endgroup$
    – Emil Jeřábek
    May 7, 2022 at 6:56

0

Reset to default

Your Answer

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