¿Está

Pensé en compartir esta pregunta, ya que podría ser interesante para otros usuarios aquí.

Suponga que una función que está en una clase uniforme (como ) también está en una pequeña clase no uniforme (como , es decir, no uniforme ), ¿esto implica que la función está contenida en un clase uniforme más pequeña (como )? Si la respuesta a esta pregunta es positiva, ¿cuál es la clase de complejidad uniforme más pequeña que contiene ? Si es negativo, ¿podemos encontrar un contraejemplo natural interesante? $NP$ $AC^0/poly$ $AC^0$ $P$ $NP \cap AC^0/poly$

¿Está contenido en ? $AC^0/poly \cap NP$ $P$

Nota: Un amigo ya respondió parcialmente mi pregunta fuera de línea, agregaré su respuesta si no la agrega él mismo.

La pregunta es mi segundo intento de formalizar la siguiente pregunta informal:

¿Puede la no uniformidad ayudarnos a calcular problemas uniformes naturales?

Relacionado:

¿Hay un candidato para un problema natural en ? $P/poly−P$

cc.complexity-theory circuit-complexity uniformity Kaveh
fuente

@Kaveh: Tal vez una pregunta interesante sería pedir un problema natural en P / poly y NP, pero no en P. (¿O tal vez esto es demasiado fácil?)

Robin Kothari

@Robin: eso parece interesante, pero no estoy seguro de que sería más fácil encontrar un problema natural en

N P \cap P / p o l y - P

$NP \cap P/poly - P$

Kaveh

@todos: necesito pensar un poco más sobre esta pregunta y las respuestas. Parece una pregunta muy natural. Pero me siento incómodo con las respuestas: primero, podemos debilitar la suposición reemplazando

con

donde

es un crecimiento muy rápido función; segundo, el contraejemplo no está solo en

N E X P \neq E X P

$NEXP \neq EXP$

N T i m e (f) \neq D T i m e (f)

$NTime(f) \neq DTime(f)$

f

$f$

A C^{0} / p o l y

$AC^0/poly$ pero tiene circuitos de tamaño 1 ya que la función es constante en todas las entradas de tamaño

para todas las

! Estas dos razones podrían estar diciendo que esta no es la pregunta correcta.

n

$n$

n

$n$

Kaveh

@Kaveh: Quizás quieras mirar la clase YP, definida por Scott Aaronson. Es como P / poly, pero el "consejo" no es confiable. En otras palabras, es como NP intersect coNP, pero el testigo solo puede depender de la longitud de entrada. YP está en P / poli, y es una clase uniforme. Quizás un problema en YP pero no en P es un ejemplo del problema que está buscando. Sería natural, uniforme, no en P, en P / poli, y posiblemente no trivial ya que el circuito debe verificar los consejos.

Robin Kothari

@Kaveh: La clase YP ("Yoda Polynomial-Time") se define más formalmente en el artículo de Scott "La capacidad de aprendizaje de los estados cuánticos" [quant-ph / 0608142]

Alessandro Cosentino

Respuestas:

Aquí hay una simplificación de la respuesta de Ryan. Supongamos que . Defina el lenguaje . El supuesto se traduce en . Además, trivialmente . $\Lambda \in NE \setminus E$ $L = \{x : |x| \in \Lambda\}$ $\Lambda \in NE \setminus E$ $L \in NP \setminus P$ $L \in AC^0/poly$

Yuval Filmus
fuente

Buena respuesta Yuval!

Dai Le

Esencialmente, la misma transformación se usa en el Libro 1974 para mostrar que E ≠ NE si y solo si NP ∖ P contiene un lenguaje de conteo.

Tsuyoshi Ito

Solo para estar seguro: ¿entiendo correctamente que

Cuál es la longitud de

escrita en unario?

| x |

$|x|$

x

$x$

Vincent

@Vincent Aquí

es una cadena en lugar de un entero, y

es su longitud

x

$x$

| x |

$|x|$

Yuval Filmus

Sí, eso es lo que me confunde. Si

es la longitud de una cadena, entonces

es un número entero, entonces, ¿cómo puede ser un elemento de

| x |

$|x|$

| x |

$|x|$

Λ

$\Lambda$

Vincent

Responda a su primera pregunta: Parece poco probable.

$NP \cap AC^0/poly \subseteq P$ $NEXP = EXP$

$C$ $C$ $C(0^n) C(0^{n-1}1) C(0^{n-2}10) \cdots C(1^n)$

$C$ $n$ $NEXP$

Ahora considera el idioma

$L =$ $1^n |$ $n$

$L$ $AC^0/poly$ $1^n$ $L$ $n$

$L$ $NP$ $n$ $\log n$ $O(n)$ $O(n)$

$L \in P$ $NEXP=EXP$ $O(n^c)$ $\log n$

Su segunda pregunta está abierta (y abierta).

Ryan Williams
fuente

¿Por qué necesitas tomar un problema completo?

Yuval Filmus

Pensé que hacía que el argumento fuera más fácil de seguir.

Ryan Williams el

Gracias Ryan por tu buena respuesta y la explicación. Supongo que no te importaría si acepto la respuesta de Yuval aunque fuiste la primera persona en publicar.

Kaveh

A la pregunta de Kaveh "¿Puede la no uniformidad ayudarnos a calcular problemas uniformes naturales?"

$n$ $1$ $n$ $n^5$ $n$

Referencias

Friedhelm Meyer auf der Heide, " Un algoritmo de búsqueda lineal polinómica para el problema de la mochila n-dimensional ", 1984

Stasys
fuente

n

$n$

2

$2$

2^{n}

$2^n$

1

$1$

N P \subseteq P / p o l y

$NP\subseteq P/poly$

@Kaveh: Pero NP en sí mismo es un gran OR de P. La "versión del tiempo" de P vs. NP es: ¿podemos reemplazar este gran OR por un árbol de decisión algebraico determinista de profundidad polinómica (con P en las hojas)? Recuerde que la profundidad trivial para Subset-Sum es 2 ^ n (no n). Dopkin y Lipton (1978) mostraron que la profundidad n ^ 2/2 es necesaria, y se creía ampliamente que esto puede mejorarse a n ^ k para cualquier k. Mayer auf der Heide refutó esta creencia: k = 5 es suficiente. Por lo tanto, la falta de uniformidad PUEDE ayudar, si estamos interesados en la profundidad (tiempo).

Stasys