¿Existe un oráculo tal que SAT no sea infinitamente frecuente en tiempo sub-exponencial?

Defina $io$ - $SUBEXP$ como la clase de lenguajes $L$ modo que haya un lenguaje $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ y para infinitamente $n$ , $L$ y $L'$ estén acuerdo en todos los casos de longitud $n$ . (Es decir, esta es la clase de lenguajes que se puede "resolver infinitamente, en tiempo subexponencial").

$A$ $NP^A \not\subset io$ $SUBEXP^A$ $A$ $SAT^A$

(Estoy haciendo preguntas separadas aquí, porque tenemos que tener cuidado con las clases de tiempo infinitamente frecuentes: solo porque tiene una reducción del problema al problema y es solucionable infinitamente a menudo, es posible que no obtenga que sea solucionable infinitamente a menudo sin más suposiciones sobre la reducción: ¿qué pasa si su reducción de "pierde" las longitudes de entrada en las que puede resolver ?) $B$ $C$ $C$ $B$ $B$ $C$

cc.complexity-theory sat oracles Ryan Williams
fuente

parece una extensión o variación de la idea de Baker Gill Solovay 1975? ¿se puede contrastar de alguna manera?

vzn

Respuestas:

Simplemente puede tomar el oráculo A st NP = EXP ya que EXP no está en io-subexp. Para SAT , depende de la codificación, por ejemplo, si las únicas instancias válidas de SAT tienen una longitud par, entonces es fácil resolver SAT en cadenas de longitud impar. Pero si usa un lenguaje como entonces debería estar bien. $^A$ $^A$ $^A$ $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$

Lance Fortnow
fuente

¿Tiene alguna referencia al concepto de clases de complejidad io y separaciones en la literatura. En particular, no estoy seguro de por qué

. Además, ¿tenemos (1)

E X P ⊈ i o

$EXP \nsubseteq io$

S U B E X P

$SUBEXP$

T I M E (f (n)) ⊈ i o

$TIME(f(n)) \nsubseteq io$

para las funciones apropiadas f (n) y (2)

implica

(o al menos

T I M E (\frac{f (n)}{\log (f (n))})

$TIME(\frac{f(n)}{\log(f(n))})$

N P \subseteq i o

$NP \subseteq io$

P

$P$

P = N P

$P = NP$

N P \subseteq P / p o l y

$NP \subseteq P/ poly$

Michael Wehar

Creo que mi principal confusión es por qué no puede cada

problema tener una

algoritmo que sólo resuelve el problema para un conjunto de longitudes de entrada

, donde

es un conjunto

E X P

$EXP$

C o m p l e t e

$Complete$

i o

$io$

S U B E X P

$SUBEXP$

X

$X$

X

$X$

E X P

$EXP$

C o m p l e t e

$Complete$

Michael Wehar

En otras palabras, el algoritmo

no nos ayuda porque tendríamos que decidir

para saber cómo usar el algoritmo

Pero, no me sorprendería si el trabajo existente de usted u otros resuelve mi consulta.

i o

$io$

S U B E X P

$SUBEXP$

X

$X$

i o

$io$

S U B E X P

$SUBEXP$

Michael Wehar

@RyanWilliams Hola Ryan, ¿alguna idea? Gracias por tu tiempo. :)

Michael Wehar

@RyanWilliams ¡Gracias por el comentario! Ayudó y creo que lo resolví. Ahora, parece que el argumento no dependía en absoluto de EXP y esto podría generalizarse para probar algo como (1). Pero, el punto clave era "el valor opuesto en al menos una entrada de esa longitud ". En otras palabras, el argumento en mi cabeza depende de que io se defina como acordar infinitamente muchas longitudes de entrada (no solo infinitamente muchas entradas). Todavía no tengo mucha idea sobre algo como (2). Gracias de nuevo y que tengan un buen día / noche. :)

Michael Wehar

No tienes que ir al límite que Lance estaba sugiriendo. Por ejemplo, en relación con un oráculo aleatorio, usar el oráculo como una función unidireccional (por ejemplo, evaluado en posiciones de bits consecutivas) es exponencialmente difícil de invertir en todas las longitudes, excepto en finitas.

Este problema se reduce directamente a SAT en la misma entrada de longitud, por lo que se deduce que SAT ^ A no está en infinitamente a menudo sub-exp.

Russell Impagliazzo
fuente

Debo decir que el número de entradas al circuito es el mismo, no el tamaño total de la instancia. Sin embargo, si se le permite rellenar tamaños de circuito agregando cláusulas redundantes, debería poder hacer que cualquier código de tamaño de entrada fijo sea una función unidireccional relacionada.

Russell Impagliazzo