¿Qué es restringido a testigos de tamaño lineal?

Esto está relacionado con la pregunta ¿Ya se conoce el tamaño de membresía de los testigos para cada idioma de NP?

Algunos problemas naturales (-completos) tienen testigos de longitud lineal: una asignación satisfactoria para , una secuencia de vértices para , etc. $\mathsf{NP}$ $SAT$ $HAMPATH$

Considere la clase de complejidad " restringida a testigos de longitud lineal". Definición formal de esta clase de complejidad, : if . $\mathsf{NP}$ $\mathcal{C}$ $L\in\mathcal{C}$ $\exists L'\in\mathsf{P}\colon (x\in L \iff \exists w\in\{0, 1\}^{O(|x|)}\colon (x, w)\in L')$

¿Es esta una clase de complejidad conocida? ¿Cuáles son sus propiedades?

cc.complexity-theory complexity-classes np argentpepper
fuente

¿No puedes lograr eso siempre rellenando?

MCH

Como señaló MCH, si es cualquier lenguaje con testigos de tamaño , entonces es un lenguaje con testigos de tamaño lineal, y y son equivalentes polinomiales de tiempo múltiple. Su clase no es exactamente , pero es básicamente la misma. La clase sugieres no es cerrado bajo polytime muchos-uno reducciones, pero por cada de existe algún lenguaje en su clase que es polytime mucho-uno equivalente a .

L

$L$

N P

$\mathsf{NP}$

O (n^{k})

$O(n^k)$

p a d (L) := {x 10^{| x |^{k}} : x \in L}

$pad(L) := \{ x10^{|x|^{k}} : x \in L\}$

N P

$\mathsf{NP}$

L

$L$

p a d (L)

$pad(L)$

N P

$\mathsf{NP}$

L

$L$

N P

$\mathsf{NP}$

L

$L$

Joshua Grochow

Respuestas:

La clase que está proponiendo probablemente no sea . (Si , entonces cada lenguaje tendría testigos de tamaño lineal, lo que implicaría que cada y , entre otras cosas) . ${\cal C}$ $NP$ ${\cal C} = NP$ $NP$ $NP \subseteq TIME[2^{O(n)}]$ $NP \neq EXP$

Es muy natural considerar tales clases; surgen en varios entornos. En este artículo , Rahul Santhanam (implícitamente) propuso la notación para el cálculo del tiempo- con bits -guess. Por lo tanto, . En este artículo , una clase análoga . (NTIBI significa "tiempo y bits no deterministas"). Además, Cai y Chen llamarían a su clase $TIGU(t(n),g(n))$ $t(n)$ $g(n)$ ${\cal C} = \bigcup_{k} TIGU(n^k,kn)$ $NTIBI[t(n),b(n)]$ $GC(O(n), P)$ (GC significa "Guess and Check", cf. L. Cai y J. Chen. Sobre la cantidad de no determinismo y el poder de verificación. SIAM Journal on Computing, 1996). Finalmente, si busca "no determinismo limitado", puede encontrar tres anotaciones más para la misma clase ...

Ryan Williams
fuente