¿Hay un candidato para un problema natural en

Quiero saber si la falta de uniformidad ayuda a las funciones informáticas en la práctica. Es fácil mostrar que hay funciones en , tome cualquier función no calificable y considere el lenguaje { }, que claramente tiene -circuitos uniformes, pero no es computable de manera uniforme en absoluto, pero este no es el tipo de funciones que me interesan. $P/poly - P$ $f$ $0^{f(n)}:n\in \omega$

¿Existe una función que sabemos que se puede calcular de manera no uniforme pero no sabemos si se puede calcular de manera uniforme (o al menos demostrar que no se puede calcular de manera uniforme no es obvio)?

¿Cómo se puede utilizar la falta de uniformidad de los circuitos para calcular funciones que no se sabe que se pueden calcular de manera uniforme (con casi la misma cantidad de recursos)?

Tenga en cuenta que no quiero funciones patológicas como la que no se puede mencionar anteriormente, quiero funciones naturales que las personas estén realmente interesadas en la computación y es plausible que se pueda o se haya podido calcular de manera uniforme.

Editar: Sé que . Entonces, una respuesta que no es un resultado de aleatorización es más interesante para mí. $BPP \subseteq P/poly$

Edición 2: Como András Salamon y Tsuyoshi Ito han dicho en sus respuestas, , y hay problemas interesantes en que no se sabe que están en , por lo que formalmente han respondido lo que he preguntado, pero eso no ayuda con lo que realmente me interesa, ya que la razón por la que están en es la posibilidad de codificar un lenguaje escaso en el circuito. Un lenguaje que no sea escaso sería más interesante. $Sparse \subset P/poly$ $Sparse$ $P$ $P/poly$

cc.complexity-theory uniformity Kaveh
fuente

@ András Salamon, @Tsuyoshi Ito: Gracias. Pero lo que me interesa es comprender cómo la falta de uniformidad puede ayudar en las funciones informáticas. El hecho de que las lenguas son escasas en

no ayuda con ella, están en

simplemente porque podemos "codificar" la mano en el circuito. Debería haber agregado el requisito a mi pregunta de que "el lenguaje no está trivialmente en

P / p o l y

$P/poly$

P / p o l y

$P/poly$

P / p o l y

$P/poly$

Kaveh

Respuestas:

No sé si esto satisface sus requisitos, pero la publicación del blog de Bill Gasarch en julio de 2010 pregunta sobre los idiomas en SPARSE ∩NP que no se consideran en P, dando un ejemplo de Ramsey Theory. Cualquiera de estos idiomas pertenece a (P / poly) ∩NP.

Relacionado con esto, para cualquier idioma L ∈NP, el idioma T _L = {1 ⁿ : L contiene una cadena de longitud n } está en TALLY ∩NP ⊆ SPARSE∩NP ⊆ (P / poly) ∩NP. Dependiendo de la elección del idioma L , T _L puede no tener una razón obvia para pertenecer a P.

Tsuyoshi Ito
fuente

La frase elegante y escasa de Tsuyoshi Ito en otra respuesta no lo dice explícitamente, pero quizás valga la pena señalar: cualquier lenguaje escaso está en P / poli. Entonces también cualquier lenguaje de conteo está en P / poly (ya que cada lenguaje de conteo es escaso).

Entonces, una forma de encontrar lenguajes "naturales" en P / poly pero no en P es buscar lenguajes dispersos "duros". Como usted señala, los "más difíciles" son los indecidibles cuando se codifican de forma dispersa, por ejemplo, en unario. En términos más generales, la versión codificada unaria de cualquier lenguaje fuera de EXP estará entonces fuera de P. (Si no, considere la máquina de Turing de tiempo exponencial que genera la codificación unaria, compuesta con la máquina que resuelve el lenguaje codificado unario resultante en el tiempo eso es polinomio en la codificación unaria. Esto es exponencial en el tamaño de la instancia original. La máquina en general se ejecuta en tiempo exponencial.) Algún lenguaje práctico de 2-EXP completo podría adaptarse a su gusto como un problema "natural".

Tenga en cuenta que el escaso lenguaje teórico de Ramsey de Bill Gasarch parece caer en la categoría de lenguajes construidos al esparcir un lenguaje difícil. Si uno codifica la instancia como un triple de números binarios en lugar de dos unarios y uno binario, entonces el color ya no es de tamaño polinómico, por lo que el lenguaje no está obviamente en NP.

András Salamon
fuente

Esto se parece más a un comentario en respuesta a la pregunta revisada (revisión 3) que a una respuesta, pero es demasiado largo para un comentario.

Simplemente excluir idiomas dispersos no es suficiente para excluir idiomas como { x ∈ {0,1} ^* : | x | ∈ S } en lugar de {1 ⁿ : n ∈ S }, donde S es un subconjunto infinito de {0, 1, 2, ...}. Me gustaría señalar que puede ser difícil distinguir entre el caso en que un lenguaje pertenece a P / poly porque es "esencialmente escaso" (como {1 ⁿ : n ∈ S } y { x : | x | ∈ S}) y el caso en que un idioma pertenece a P / poly por otros motivos. Lo problemático aquí es, obviamente, cómo definir el término "esencialmente escaso".

Es posible que desee definir "escasez esencial" de la siguiente manera: un lenguaje es esencialmente escaso si es reducible a un lenguaje escaso. Sin embargo, se debe tener cuidado porque si usa la reducibilidad de Turing en tiempo polinómico en esta definición, ¡la definición es equivalente a la membresía de P / poly!

Entonces, una cosa obvia para intentar es usar la reducibilidad de tiempo múltiple polinomial. No sé si esto es equivalente a la pertenencia a P / poly, y mucho menos si P / poly contiene algún lenguaje natural que no sea esencialmente escaso en este sentido.

Tsuyoshi Ito
fuente

En realidad, pensé en esto cuando vi las respuestas antes de modificar la pregunta, ya que era natural pensar en una combinación booleana de idiomas dispersos. Pensé que excluir los idiomas que son

reducibles a idiomas dispersos (o tal vez un poco más) debería ser suficiente para mi pregunta, pero parece que esto es más complicado de lo que pensaba.

A C^{0}

$AC^0$

Kaveh

@Kaveh: Esa puede ser otra buena definición de "esencialmente escaso". Al leer su comentario, me pregunto si P / poly = P∪ (AC0 / poly) (supongo que no), porque cualquier problema en (P / poly) ∖ ( Podría decirse que P∪ (AC0 / poli)) podría ser "computable mediante el uso de una familia no uniforme de circuitos de tamaño polinomial combinando realmente el poder de los circuitos de tamaño polinómico y el poder de la no uniformidad".

Tsuyoshi Ito

Un posible problema con mi definición basada en uno de sus ejemplos es si el siguiente lenguaje es esencialmente escasa : verificación si el número de unos en la entrada está en un lenguaje escasa

. (En términos más generales, sea

un problema de función completa para la clase de complejidad

y sea

un lenguaje escaso. Piense en

como si tuviera un rango amplio similar a la función NumOnes. Sea

el conjunto de

s st

)

S

$S$

f

$f$

C

$C$

S

$S$

f

$f$

L

$L$

x

$x$

f (x) \in S

$f(x) \in S$

Kaveh

[continuación] Otra clase de idiomas: tome un lenguaje escaso

y un lenguaje

completo para la clase de complejidad

y luego considere la concatenación

(

donde cada símbolo se reemplaza con dos copias del mismo, por ejemplo 010 se convierte en 001100) También se puede requerir que la longitud de la segunda parte en la concatenación sea menor que la longitud de la primera parte. Estos idiomas satisfacen todas las condiciones, excepto que son un problema natural que la gente está realmente interesada en resolver.

S

$S$

A

$A$

C

$C$

L = A^{'} .01 . S^{'}

$L=A'.01.S'$

A^{'}

$A'$

A

$A$

Kaveh

@Kaveh: Hmm, ya veo. Gracias por compartir los ejemplos. Retiro la idea de ver (P / poly) ∖ (P∪ (AC0 / poly)) como "P / poly por razones no triviales". Si no me equivoco, ambos ejemplos son polinomiales en tiempo múltiple reducibles a un lenguaje escaso, por lo que todavía hay alguna esperanza de que la definición de "escasez esencial" que sugerí en la respuesta sea adecuada.

Tsuyoshi Ito