Problemas abiertos en las fronteras de TCS

58

En el hilo ¿ Principales problemas no resueltos en informática teórica? , Iddo Tzameret hizo el siguiente excelente comentario:

Creo que deberíamos distinguir entre los principales problemas abiertos que se consideran problemas fundamentales, como PNP , y los principales problemas abiertos que constituirán un avance técnico, si se resuelven, pero no son necesariamente tan fundamentales, por ejemplo, límites inferiores exponenciales en AC0(6) Circuitos C 0 ( 6 ) (es decir, compuertas ). Por lo tanto, posiblemente deberíamos abrir una nueva wiki de la comunidad titulada "problemas abiertos en las fronteras de TCS", o similares.AC0+mod6

Como Iddo no inició el hilo, pensé que comenzaría este hilo.

A menudo, los principales problemas abiertos de los campos son conocidos por los investigadores que trabajan en campos relacionados, pero los extraños desconocen el punto en el que la investigación actual está estancada. El ejemplo citado es bueno. Como un extraño, está claro que uno de los mayores problemas en la complejidad del circuito es demostrar que NP requiere circuitos de tamaño superpolinomial. Pero los extraños pueden no ser conscientes de que el punto actual en el que estamos atascados está tratando de probar límites inferiores exponenciales para circuitos AC 0 con puertas mod 6. (Por supuesto, podría haber otros problemas de complejidad de circuito de dificultad similar que describirían dónde estamos atascados. Esto no es único). Otro ejemplo es mostrar los límites inferiores de espacio-tiempo para SAT mejor que n 1.801 .

Este hilo es para ejemplos como este. Como es difícil caracterizar tales problemas, solo daré algunos ejemplos de propiedades que poseen tales problemas:

  1. A menudo no serán los grandes problemas abiertos del campo, pero serán un gran avance si se resuelven.
  2. Por lo general, no es increíblemente difícil, en el sentido de que si alguien le dijera que el problema se resolvió ayer, esto no sería demasiado difícil de creer.
  3. Estos problemas también suelen tener números o constantes que no son fundamentales, pero surgen porque es donde estamos atascados.
  4. El problema en las fronteras de un campo en particular seguirá cambiando de vez en cuando, a diferencia del mayor problema en el campo, que seguirá siendo el mismo durante muchos años.
  5. A menudo, estos problemas son los problemas más fáciles que aún están abiertos. Por ejemplo, tampoco tenemos límites inferiores exponenciales para AC 1 , pero dado que [6] está incluido en esa clase, es formalmente más fácil mostrar límites inferiores para [6], y así es La frontera actual de la complejidad del circuito. A C 0AC0AC0

Por favor, publique un ejemplo por respuesta; se aplican las convenciones estándar de lista grande y CW. Si alguien puede explicar qué tipo de problemas estamos buscando mejor que yo, no dude en editar esta publicación y hacer los cambios apropiados.

EDITAR: Kaveh sugirió que las respuestas también incluyen una explicación de por qué un problema dado está en la frontera. Por ejemplo, ¿por qué estamos buscando límites inferiores contra AC 0 [6] y no AC 0 [3]? La respuesta es que tenemos límites inferiores contra AC 0 [3]. Pero la pregunta obvia es por qué esos métodos fallan para AC 0 [6]. Sería bueno si las respuestas pudieran explicar esto también.

Robin Kothari
fuente
1
¿Se trata solo de la teoría de la complejidad? Pregunto porque en el hilo citado, hay muchos problemas que encajarían en la descripción establecida de esta pregunta, y tampoco tienen una relación directa con P vs NP (distancia de edición, multiplicación de matrices, etc.)
Suresh Venkat
Tenía la intención de incluir todos los TCS. Solo utilicé ejemplos de complejidad porque con eso estoy familiarizado. Habrá cierta superposición con ese hilo ya que las personas publicaron importantes problemas abiertos y problemas en la frontera de nuestro conocimiento.
Robin Kothari
3
Creo que esta es una excelente pregunta, mucho más interesante y útil que la que se refiere a los "principales problemas abiertos". Por lo tanto, decidí comenzar una recompensa, aunque esta no era mi pregunta. No estoy 100% seguro de lo que sucede si doy una recompensa por una respuesta de CW, pero lo veremos en 7 días. :)
Jukka Suomela
1
Buena idea. También tengo curiosidad por saber qué sucede si otorgas una recompensa por una respuesta de CW.
Robin Kothari
Y la recompensa fue a la respuesta actual de alto rango. (Parece que funcionó como se esperaba; el usuario que publicó la respuesta CW obtuvo +50 rep.)
Jukka Suomela

Respuestas:

27

Aquí hay tres en los caminos más cortos de investigación:

O ( n + m log w ) 2 w1 . ¿Existe un algoritmo de tiempo lineal para las rutas más cortas de una sola fuente en gráficos dirigidos con pesos no negativos, al menos en el modelo de cómputo de palabra-RAM? Tenga en cuenta que existe un algoritmo de tiempo lineal para gráficos no dirigidos (consulte el documento de Thorup). En base a eso, Hagerup tiene un tiempo de ejecución de para gráficos dirigidos con pesos delimitados por . ¿Hay un algoritmo más rápido?O(n+mlogw)2w

O ( n ω n ) ω < 2.376 O ( n 2.575 ) O ( n ω n )2 . ¿Existe un algoritmo polylog para todos los pares de rutas más cortas en gráficos dirigidos no ponderados? ( es el exponente de la multiplicación de matrices) El mejor tiempo de ejecución actual es por Zwick, y para gráficos no dirigidos el problema puede resolverse en polylog .O(nωn)ω<2.376O(n2.575)O(nωn)

(¿Los problemas dirigidos son realmente más difíciles?)

O ( n 2.9 ) n 0 , , n3 . ¿Existe un algoritmo para todos los pares de rutas más cortas en gráficos de nodo con pesos en { }? ¿O hay una reducción del problema general de todos los pares de caminos más cortos a esta restricción?O(n2.9)n0,,n

virgi
fuente
22

Esto ya se menciona en la pregunta:

Abierto:

Separe de ( circuitos de profundidad 2). A C 0 2 [ 6 ] A C 0 [ 6 ]EXPNPAC20[6]AC0[6](ver la actualización a continuación)

[Nov. 11, 2010] Separe de . Separe de .A C 0 2 [ 6 ] E X P N P T C 0EXPAC20[6]EXPNPTC0

Conocido:

  1. [Alexander Razborov 1987 - Roman Smolensky 1987] no está en si es primo no es una potencia de . A C 0 [ p k ] p m pMODmAC0[pk]pmp

  2. [Arkadev Chattopadhyay y Avi Wigderson 2009] Sea m, q sean enteros co-primos, de modo que m esté libre de cuadrados y tenga como máximo dos factores primos. Supongamos que C sea cualquier circuito de tipo donde es la puerta u y las puertas en la base tienen conjuntos de aceptación arbitrarios. Si C calcula entonces el fan-in superior, y por lo tanto el tamaño del circuito, debe ser . G A N D O R M O D m M O D q 2 Ω ( n )MAJoGoMODmAGANDORMODmMODq2Ω(n)

El resultado posterior se basa en obtener un límite de correlación exponencialmente pequeño de la función con subcircuitos de profundidad-2 y estimar sumas exponenciales que involucran polinomios de bajo grado.MODq

Obstáculos:


Actualización [nov. 10 de 2010]

Un artículo de Ryan Williams parece haber resuelto este problema abierto utilizando métodos que parecen ser esencialmente diferentes de los mencionados anteriormente:

[Ryan Williams 2010] no tiene circuitos no uniformes de tamaño . A C C 0 2 n o ( 1 )ENPACC02no(1)


Referencias

  • AA Razborov. Límites inferiores sobre el tamaño de las redes de profundidad limitada sobre una base completa con adición lógica (ruso), en Matematicheskie Zametki, 41 (4): 598–607, 1987. Traducción al inglés en Notas Matemáticas de la Academia de Ciencias de la URSS, 41 (4): 333–338, 1987.

  • R. Smolensky. Métodos algebraicos en la teoría de los límites inferiores para la complejidad del circuito booleano. En STOC, páginas 77–82. ACM, 1987.

  • Arkadev Chattopadhyay y Avi Wigderson. Sistemas lineales sobre módulos compuestos , FOCS 2009

  • Ryan Williams. Límites inferiores del circuito ACC no uniforme , 2010, borrador (¿presentado?).

Kaveh
fuente
1
¿Es NP la clase más grande que no se sabe que incluye estrictamente [6]? AC0
Robin Kothari
1
Supongo que [6] aquí se refiere a la versión no uniforme de la clase (de lo contrario, estaría estrictamente contenida en EXP ya que está contenida en P). Quizás alguien también pueda agregar el estado actual de conocimiento para la versión uniforme. AC0
Robin Kothari
44
Para aclarar: si los límites inferiores son conocidos para los circuitos de profundidad 2 depende crucialmente de la definición exacta de puertas . Si definimos (como se hace principalmente) si y solo si entonces se conocen los límites inferiores . De entrar en territorio pregunta abierta, permitiendo "generalizadas" criterios de aceptación, es decir puertas que son 1 si la suma módulo 6 se encuentra en para algunos . AC0\[6\]MOD6MOD6(x)=1xi0(mod6) A A { 0 , , 5 }MOD6AAA{0,,5}
Kristoffer Arnsfelt Hansen
2
Un punto adicional: si aumenta la profundidad de 2 a 3, entonces la distinción entre puertas ya no importa ... no se conocen límites inferiores para ninguno de los tipos de puerta. MOD6
Ryan Williams
11
Ahora este es resuelto por Ryan: cs.cmu.edu/~ryanw/acc-lbs.pdf . ¡¡¡Felicidades!!!
Hsien-Chih Chang 張顯 之
20

Deje que CNF-SAT sea el problema de determinar si una fórmula CNF dada es satisfactoria (sin restricciones en el ancho de las cláusulas).

¿Es CNF-SAT en variables y cláusulas solucionables en tiempo, por algún ?m 2 δ n p o l y ( m ) δ < 1nm2δnpoly(m)δ<1

Este es un problema abierto bien conocido en el área de "algoritmos más rápidos para NP". No creo que haya alcanzado el estado de "gran problema abierto", pero ha atraído bastante atención. Los algoritmos más conocidos se ejecutan en tiempo (por ejemplo, aquí ).2nΩ(n/log(m/n))

En relación con la hipótesis de tiempo exponencial (que 3SAT no está en tiempo subexponencial), también existe una "hipótesis de tiempo exponencial fuerte" en la que el tiempo de ejecución óptimo para -SAT converge a como . Una consecuencia de Strong-ETH sería que la respuesta a la pregunta anterior es no. Varias hipótesis plausibles implican que la respuesta es sí , pero quién sabe.2 n k k2nk

Creo que es uno de esos problemas que parecen "resolverse" de cualquier manera: mostraremos una respuesta afirmativa o mostraremos que una respuesta afirmativa implica algo muy importante. En el primer caso, tendremos la satisfacción de resolver el problema, en el segundo caso habremos elevado la pregunta a la de un "problema abierto importante" ... una no respuesta implica , y Una respuesta afirmativa implica algo muy importante. :)PNP

Ryan Williams
fuente
18

La cuestión de si los árboles de decisión son aptos para PAC parece estar en la frontera de la teoría del aprendizaje computacional.

ABIERTO

¿Los árboles de decisión (DT) PAC se pueden aprender bajo la distribución uniforme en los ejemplos (o en general)?

CONOCIDO

  • Los DT no se pueden aprender bajo la distribución uniforme con consultas estadísticas (SQ) [ Blum et al. '94 ]
  • Los DT aleatorios se pueden aprender bajo la distribución uniforme [ Jackson, Servedio '05 ]
  • Los DT monótonos se pueden aprender bajo la distribución uniforme [ O'Donnell, Servedio '06 ]
  • un análisis suavizado para aprender DT bajo la distribución uniforme [ Kalai, Teng '08 ]

La razón por la cual este es un problema interesante e importante es porque los árboles de decisión son una clase muy natural y, a diferencia de, digamos autómatas, no tenemos resultados de dureza criptográfica que hagan que el problema sea irremediable. El progreso en esta cuestión quizás pueda dar una idea de si los DT (y clases similares) se pueden aprender sin suposiciones de distribución. Esto podría tener un impacto práctico además de ser un avance teórico.

Este problema también parece haber sido abordado desde todos los lados. Sabemos que bajo la distribución uniforme de los ejemplos: los árboles de decisión monótonos se pueden aprender, que los árboles de decisión aleatorios se pueden aprender, y que también existe un análisis suavizado. También sabemos que un algoritmo SQ no resolverá este problema. Y también hay un progreso constante en esta área. Por otro lado, este es un problema difícil que ha estado abierto durante un tiempo, por lo que parece encajar en la lista de "Problemas abiertos en las fronteras de TCS".

Tenga en cuenta que hay otros resultados que no analicé sobre la dureza de los DT de aprendizaje adecuados , la capacidad de aprender DT con consultas y la dureza de aprender incluso DT aleatorios con SQ.

Lev Reyzin
fuente
16

ABIERTO:

Muestre un límite inferior en el modelo de sonda de celda para un problema explícito de estructuras de datos estáticos, que demuestra que bajo alguna restricción de espacio "razonable" (por ejemplo, que el espacio es polinómico en el tamaño de la entrada), entonces el tiempo de consulta debe estar en menos T, donde T es mayor que log | Q |, donde Q es el conjunto de consultas. A esto se le llama "log | Q | -barrier" (o, a veces, de una manera un tanto errónea, la "barrera logn").

CONOCIDO:

  1. límites inferiores superiores a log | Q | para un problema implícito (ver la encuesta de Miltersen )

  2. límites inferiores superiores a log | Q | con restricciones de espacio extremas (p. ej., límites inferiores sucintos)

  3. límites inferiores superiores a log | Q | para problemas dinámicos (donde quiero decir que si el tiempo de actualización es muy pequeño, entonces el tiempo de consulta debe ser muy grande, o viceversa; ver, por ejemplo, el límite inferior de Patrascu para una suma parcial)

  4. Límites inferiores en modelos restringidos, como máquinas de puntero, modelo de comparación, etc.

  5. límites inferiores que rompen el registro | Q | el tipo estándar de reducción de la complejidad de la comunicación no puede demostrar la barrera, porque Alice solo puede enviar la consulta en sí, que solo requiere log | Q | bits, y por lo tanto es fácil verificar que la reducción nunca dará un límite inferior mejor que este. Por lo tanto, se debe usar un "nativo" vinculado al modelo de sonda celular, o se debe usar una reducción más inteligente de la complejidad de la comunicación.

Elad
fuente
1
Quizás estoy malinterpretando la pregunta, pero ¿cómo se sabe esto? "Límites inferiores más altos que log | Q | para problemas dinámicos (¿referencia?)"
Mihai
agregó la referencia apropiada y aclaró.
Elad
16

En las clases de complejidad de bajo nivel, hay un problema interesante sobre la caracterización de .NL

ABIERTO:

Muestre que si es igual a .U LNLUL

N LUL , el espacio de registro inequívoco , es la clase que consta de problemas que pueden resolverse mediante una con la restricción adicional de que hay como máximo una ruta de cálculo aceptable.NL

CONOCIDO:

  • En circunstancias no uniformes , . [RA00]NL/poly=UL/poly
  • Bajo supuestos plausibles de dureza ( requiere circuitos de tamaño exponencial), el resultado de [RA00] puede ser aleatorizado para mostrar que . [ARZ99]N L = U LSPACE(n)NL=UL
  • La accesibilidad en gráficos de 3 páginas está completa para . [PTV10]NL
  • La accesibilidad en gráficos de 2 páginas se puede resolver para . [BTV09]UL
  • Si , entonces . [AJ93]NL=ULFNLL

DESCONOCIDO:

  • Una clase intermedia , que se define como problemas que puede resolver una con como máximo polinómicamente muchas rutas de cálculo de aceptación, se encuentra entre y . No se conocen colapsos.FewLNLNLUL
  • Se sabe que por el famoso teorema Immerman-Szelepcsényi, mientras que si está cerrado bajo el complemento aún está abierto.NL=coNLUL
Hsien-Chih Chang 張顯 之
fuente
3
es posible que desee agregar NL = coNL, es un resultado clásico pero está relacionado.
Kaveh
1
@Kaveh: ¿Quiere decir que si UL está cerrado bajo complemento?
Hsien-Chih Chang 張顯 之
1
¡Entendido! Perdón por el malentendido ... Lo puse en la parte DESCONOCIDA en su lugar, para enfatizar como una propiedad de UL.
Hsien-Chih Chang 張顯 之
15

Algunos problemas abiertos de PCP:

  • La conjetura de escala móvil. En PCP queremos que el error del verificador sea lo más pequeño posible. BGLR conjeturó que el error puede llegar hasta donde es la aleatoriedad (claramente hay un límite inferior ). El precio que paga por disminuir el error solo aumenta el alfabeto de manera adecuada.2Θ(r)r2r

Más formalmente: la conjetura es que existe ac, de modo que para todo r natural, para todo , hay un verificador PCP que usa aleatoriedad r para hacer dos consultas a su prueba, tiene perfecto error de integridad y solidez . El alfabeto de la prueba depende solo de .ε2crε1/ε

Para dos consultas, el error más conocido es para algunos específicos (M-Raz, 2008). También se puede lograr el error para cualquier , con una serie de consultas que dependen de (DFKRS).1/rββ>02rαα<1α

También se buscan límites inferiores en c (es decir, algoritmos de aproximación).

Vea la encuesta de Irit Dinur para más detalles.

  • Longitud lineal PCP. Hay códigos de corrección de errores de alta distancia con longitud lineal. ¿Hay un PCP con longitud lineal?

Específicamente, ¿queremos un verificador para la satisfacción de una fórmula SAT que tenga un número constante de consultas, un alfabeto constante y un error constante, y acceda a una prueba de longitud lineal en la longitud de la fórmula? Esto está abierto incluso para errores cercanos a 1 (pero mejores que el trivial ), alfabeto sub-exponencial y número de consultas sub-lineal.11/n

La longitud más conocida es para error constante, y para error subconstante.npolylognn2(logn)1β

Dana Moshkovitz
fuente
14

Demuestre que para cada , hay un lenguaje en que no tiene circuitos (no uniformes) con cables . Recuerde que . Es decir, probar los límites inferiores del circuito superlineal durante un tiempo exponencial con acceso a un oráculo .E N P c n E = k 1 T I M E [ 2 k n ] N Pc>0ENPcnE=k1TIME[2kn]NP

Ryan Williams
fuente
¿Cuál es la clase más pequeña para la que tenemos límites inferiores del circuito superlineal?
Robin Kothari
@Robin: Buena pregunta. No hay realmente un mínimo "único" aquí. En términos de "clases ligadas polinomiales", se sabe que la clase no tiene circuitos superlineales. También se pueden probar los límites inferiores del circuito superlineal para para sin límites . (Permítanme dejar esto como un ejercicio ... pista: el conjunto de todos los circuitos de tamaño tiene cardinalidad .)S2PZPPNPTIME[2f(n)nlogn]fcn2O(nlogn)
Ryan Williams
14

A -el código decodificable localmente (LDC) es un mapa tal que hay un algoritmo , llamado decodificador local , que, dado como entrada, un entero y una palabra recibida que difiere de para algunos como máximo fracción de posiciones, busca la mayoría de las coordenadas de y genera con una probabilidad de al menos . Se dice que el LDC es lineal si(q,δ,ϵ)C:FmFnAi[m]yFnC(x)xFmδqyxi1/|F|+ϵFes un campo y es -lineal. Los LDC tienen muchas aplicaciones en teoría de la complejidad y privacidad, entre otras.CF

Para y constante , la situación está completamente resuelta. El código Hadamard es un LDC lineal de con , y se sabe que es esencialmente óptimo, incluso para los LDC no lineales. Pero aquí, es la frontera! Tan pronto como hacemos , hay una gran brecha entre los límites superior e inferior conocidos. El mejor límite superior actual es un LDC lineal de sobre cualquier campo finito (e incluso los reales y complejos) con complejidad de consulta [ Efremenko '09 , Dvir-Gopalan-Yekhanin '10 ]. Los mejores límites inferiores sonq=2δ,ϵ2n=exp(m)q=2q=33n=exp(exp(logmloglogm))=2mo(1)Ω(m2) para LDC lineales de sobre cualquier campo y para LDC generales de [ Woodruff '10 ]. La situación para un mayor número de consultas es aún más grave.3Ω(m2/logm)3

revs arnab
fuente
13

¿Cuál es la mayor brecha posible entre las complejidades de consulta cuántica determinista y (error acotado de 2 lados) para funciones totales?

Abierto:

¿Existe una función total cuya complejidad de consulta cuántica es T y la complejidad de consulta determinista es ω (T 2 )?

¿Existe una función total cuya complejidad de consulta cuántica es T, y la complejidad de consulta determinista es ω (T 4 )?

Si una función total puede calcularse con consultas T mediante un algoritmo cuántico, ¿puede calcularse siempre mediante consultas mediante un algoritmo determinista?o(T6)

Conocido:

Si la complejidad de consulta cuántica de una función total es T, su complejidad de consulta determinista es . (Referencia)O(T6)

La mayor brecha conocida se logra mediante la función OR, que logra una brecha cuadrática.

Actualización (21 de junio de 2015) : ahora conocemos una función que logra una separación de cuarto (4to poder). Ver http://arxiv.org/abs/1506.04719 .

Se conjetura que la función OR logra el espacio máximo posible.


Según la sugerencia de Ashley, permítanme agregar el mismo problema para el cálculo exacto.

Abierto:

¿Existe una función total cuya complejidad de consulta cuántica exacta sea T y cuya complejidad de consulta determinista sea ?ω(T)

Conocido:

Si la complejidad de consulta cuántica exacta de una función total es T, su complejidad de consulta determinista es . (Referencia)O(T3)

La brecha más conocida es un factor de 2.

Actualización (5 de noviembre de 2012) : Andris Ambainis ha mejorado esta ventaja en Superlinear para algoritmos cuánticos exactos . Del resumen: "Presentamos el primer ejemplo de una función booleana f (x_1, ..., x_N) para la cual los algoritmos cuánticos exactos tienen una ventaja superlineal sobre los algoritmos deterministas. Cualquier algoritmo determinista que calcule nuestra función debe usar N consultas pero un El algoritmo cuántico exacto puede calcularlo con O (N ^ {0.8675 ...}) consultas ".

Robin Kothari
fuente
2
Este es uno de mis problemas abiertos favoritos también. Pero también agregaría la siguiente pregunta: ¿existe una función total cuya complejidad cuántica de consulta exacta sea T y cuya complejidad de consulta determinista sea ω (T) ? La brecha más conocida es un factor de 2. Me resulta un tanto sorprendente que este sea un problema abierto.
Ashley Montanaro
11

Hay una serie de problemas abiertos en la complejidad de la prueba, mencionaré solo uno que permanece abierto incluso después de que algunos expertos pasaron años tratando de resolverlo. Es la versión de prueba de complejidad del estado en complejidad de circuito. (Consulte [Segerlind07] si desea ver más problemas abiertos en la complejidad de la prueba).

Abierto

Demuestre los límites inferiores del tamaño de la prueba superpolinómica para el sistema de prueba -Frege.AC0[2]

AC0[2] -Frege (también conocido como d-Frege + ) es el sistema a prueba de proposiciones que solo permite circuitos ( con puertas).CG2AC0[2]AC0mod2

Conocido

  1. Hay un tamaño de prueba exponencial en el límite inferior para -Frege (también conocido como Frege de profundidad constante, d-Frege) para (formulación proposicional del Principio de Pigeon-Hole con palomas y agujeros). También hay límites inferiores exponenciales para -Frege + (Frege de profundidad constante con contar axioms). También se sabe que -Frege + no están polinómicamente delimitados.AC0PHPnn+1n+1nAC0CApmodpAC0CAm

  2. Existen límites inferiores de tamaño de circuito exponencial para la clase de circuito correspondiente, a saber, .AC0[2]


Referencias

  • Nathan Segerlind, "La complejidad de las pruebas proposicionales", Boletín de lógica simbólica 13 (4), 2007
Kaveh
fuente
9

Abierto:

Mostrar una separación de oráculo entre QIP (2) y AM. Es decir, mostrar un problema en proyectos de efecto rápido (2) A que no está en AM A .

El gran problema abierto es mostrar una separación de oráculo entre BQP y PH. Pero ni siquiera tenemos una separación entre BQP y AM (dado que AM está en PH, esto debería ser más fácil). Peor aún, haga que BQP sea considerablemente más poderoso al permitir interacciones de 1 ronda con Merlin, dándole la clase QAM o QIP (2) (dependiendo de monedas públicas o monedas privadas) y todavía no tenemos una separación.

Conocido:

La separación más conocida es entre BQP y MA, que proviene de este artículo de John Watrous . Para las clases de complejidad que no son clases de problemas de decisión, vea estos resultados de Scott Aaronson .

Robin Kothari
fuente
4

No estoy seguro de si esto pertenece a la clase de problemas abiertos de frontera o problemas abiertos importantes , por lo que los comentarios son bienvenidos.

Abierto:

Muestre que si implica colapsa o no.NP=UPPH

UP (el tiempo polinómico inequívoco ) es una clase definida como problemas de decisión decididos por una máquina NP con una restricción adicional que

  • a lo sumo hay una ruta de cálculo de aceptación en cualquier entrada.

Este problema ha sido declarado en el blog de complejidad en 2003.

Conocido:

Un resultado de Hemaspaandra, Naik, Ogiwara y Selman muestra que si se cumple la siguiente declaración, la jerarquía polinómica se colapsa al segundo nivel.

  • Hay una lenguaje tal que para cada fórmula en SAT, hay una única asignación satisfacer con en . L ϕ x ( ϕ , x ) LNPLϕx(ϕ,x)L

Desconocido:

Cualquier colapso o separación improbable.

Publicación relacionada: Más información sobre las clases sintácticas vs semánticas, y UP vs NP .

Hsien-Chih Chang 張顯 之
fuente
¿Hay alguna declaración más débil también abierta? Por ejemplo, ¿MA = UP implica un colapso? o AM = ARRIBA?
Robin Kothari
@ Robin: En mi conocimiento, no. Pero soy nuevo en esta área y sigo estudiando los resultados. ¡Quizás surja algo relevante!
Hsien-Chih Chang 張顯 之