26
$\begingroup$

This is related to the question Is the Witness Size of Membership for Every NP Language Already Known?

Some natural $\mathsf{NP}$(-complete) problems have linear length witnesses: a satisfying assignment for $SAT$, a sequence of vertices for $HAMPATH$, etc.

Consider the complexity class "$\mathsf{NP}$ restricted to linear length witnesses". Formal definition of this complexity class, call it $\mathcal{C}$: $L\in\mathcal{C}$ if $\exists L'\in\mathsf{P}\colon (x\in L \iff \exists w\in\{0, 1\}^{O(|x|)}\colon (x, w)\in L')$.

Is this a known complexity class? What are its properties?

Improve this question
$\endgroup$
2
  • $\begingroup$ Can't you always achieve that by padding? $\endgroup$
    – Mahdi Cheraghchi
    Commented May 9, 2012 at 18:36
  • 5
    $\begingroup$ As MCH pointed out, if $L$ is any $\mathsf{NP}$ language with witnesses of size $O(n^k)$, then $pad(L) := \{ x10^{|x|^{k}} : x \in L\}$ is an $\mathsf{NP}$ language with linear-size witnesses, and $L$ and $pad(L)$ are polynomial-time many-one equivalent. Your class isn't quite $\mathsf{NP}$, but it's basically the same. The class you suggest is not closed under polytime many-one reductions, but for every $L$ in $\mathsf{NP}$ there is some language in your class that is polytime many-one equivalent to $L$. $\endgroup$
    – Joshua Grochow
    Commented May 9, 2012 at 19:54

1 Answer 1

Reset to default
29
$\begingroup$

The class ${\cal C}$ you are proposing is probably not $NP$. (If ${\cal C} = NP$, then every $NP$ language would have linear-size witnesses, which would imply that every $NP \subseteq TIME[2^{O(n)}]$ and $NP \neq EXP$, among other things).

It is very natural to consider such classes; they arise in several settings. In this paper, Rahul Santhanam (implicitly) proposed the notation $TIGU(t(n),g(n))$ for time-$t(n)$ computation with $g(n)$-guess bits. Hence ${\cal C} = \bigcup_{k} TIGU(n^k,kn)$. In this paper, I defined an analogous class $NTIBI[t(n),b(n)]$. (NTIBI stands for "nondeterministic time and bits".) Also, Cai and Chen would call your class $GC(O(n), P)$ (GC stands for "Guess and Check", cf. L. Cai and J. Chen. On the amount of nondeterminism and the power of verifying. SIAM Journal on Computing, 1996). Finally, if you search for "bounded nondeterminism" you may find three more notations for the same class...

Improve this answer
$\endgroup$
0

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.