Skip to main content
Theoretical Computer Science

Return to Question

replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

This is related to the question Is the Witness Size of Membership for Every NP Language Already Known?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?

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?

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?

Tweeted twitter.com/#!/StackCSTheory/status/200589789035106304
Source Link
argentpepper
argentpepper
  • 2.3k
  • 15
  • 27

What is $\mathsf{NP}$ restricted to linear size witnesses?

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?