# Nondeterministic polynomial time languages with linearly bounded certificates

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 ?

• 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. May 7, 2022 at 6:56