Una antología de supuestos de complejidad

32

En el artículo The Random Oracle Hypothesis Is False , los autores (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan y Rohatgi) discuten las implicaciones de la hipótesis del oráculo aleatorio . Argumentan que sabemos muy poco acerca de las separaciones entre clases de complejidad, y la mayoría de los resultados implican el uso de supuestos razonables o la hipótesis del oráculo aleatorio. La suposición más importante y ampliamente creída es que el PH no colapsa. En sus palabras:

En un enfoque, asumimos como hipótesis de trabajo que el PH tiene infinitos niveles. Por lo tanto, cualquier suposición que implique que el PH es finito se considera incorrecta. Por ejemplo, Karp y Lipton mostraron que si NP ⊆ P / poli, entonces PH colapsa a . Entonces, creemos que SAT no tiene circuitos de tamaño polinómico. Del mismo modo, creemos que los conjuntos completos de Turing y muchos completos para NP no son escasos, porque Mahaney demostró que estas condiciones colapsarían el PH. Incluso se puede demostrar que para cualquier k ≥ 0, implica que el PH es finito. Por lo tanto, creemos queΣ2PPSAT[k]=PSAT[k+1]PSAT[k]PSAT[k+1] para todos los k ≥ 0. Por lo tanto, si la jerarquía polinómica es realmente infinita, podemos describir muchos aspectos de la complejidad computacional de NP.

Además del supuesto de que el PH no se colapsa, ha habido muchos otros supuestos de complejidad. Por ejemplo:

  1. Yao considera plausible la siguiente suposición: .RPϵ>0DTIME(2nϵ)
  2. Nisan y Wigderson hacen varias suposiciones relacionadas con la desrandomización.

La idea principal de esta pregunta es lo que dice su título: Ser una antología de supuestos teóricos de complejidad. Sería genial si se cumplieran las siguientes convenciones (siempre que sea posible):

  1. La suposición misma;
  2. El primer documento en el que se hace la suposición;
  3. Resultados interesantes en los que se utiliza el supuesto;
  4. Si el supuesto alguna vez ha sido refutado / probado, o si su plausibilidad ha sido discutida alguna vez.

This post is meant to be a community wiki; if an assumption is already cited, please edit the post and add new information rather than making a new post.


Editar (31/10/2011): algunos supuestos criptográficos e información sobre ellos se enumeran en los siguientes sitios web:

  1. Wiki de primitivas criptográficas y problemas difíciles en criptografía .
  2. Supuestos criptográficos y problemas difíciles de Helger Lipmaa .
Sadeq Dousti
fuente
2
Agradable. David Johnson hizo algo similar para los resultados de complejidad utilizados para mostrar la dureza de la aproximación en una columna reciente.
Suresh Venkat
@Suresh: Un enlace a la columna de Johnson es muy apreciado.
MS Dousti
Requerir el primer artículo puede ser complicado.
András Salamon
@ András: Sí. Por esa razón, agregué la frase "siempre que sea posible". Puedes citar el papel que crees que es el primero. Como se trata de CW, si alguien conoce un resultado anterior, simplemente corrige la publicación.
MS Dousti

Respuestas:

10
  • Suposición: hipótesis de tiempo exponencial .
  • Citado por primera vez en: Mientras era folklore, se formalizó por primera vez en el siguiente artículo: Russell Impagliazzo y Ramamohan Paturi. 1999. La complejidad de k-SAT . En Actas de la Decimocuarta Conferencia Anual de IEEE sobre Complejidad Computacional ( COCO '99 ). IEEE Computer Society, Washington, DC, EE. UU., 237-240.
  • Uso (s): Asume que no se puede decidir ningún problema de NP completo en un tiempo sub-exponencial, y por lo tanto implica que P ≠ NP.
  • Estado: abierto.
Increíble
fuente
Supongo que ETH supone que el problema 3-SAT no se puede decidir en un tiempo sub-exponencial. Las respuestas a esta publicación ( cstheory.stackexchange.com/questions/3620/… ) implican la existencia de algoritmos de tiempo sub-exponenciales para algunos problemas completos de NP, como el Conjunto Independiente Planar.
Mohammad Al-Turkistany
Como escribe Mohammad, la descripción en "Uso (s)" es imprecisa o simplemente incorrecta.
Yoshio Okamoto
@YoshioOkamoto: Esta es una publicación wiki de la comunidad. ¿Por qué no seguir adelante y hacer que la publicación sea precisa, o incluso corregirla?
MS Dousti
No estoy seguro. La página de Wikipedia vinculada contiene más información, y mi edición sería solo una repetición.
Yoshio Okamoto
8
  • Supuesto : NP no tiene medida p 0
  • Citado por primera vez en : Jack H. Lutz. Categoría y medida en clases de complejidad . SIAM J. Comput. 19: 1100-1131, 1990.
  • μpags(nortePAGS)0 0PAGSnortePAGS
    1. Tpagsmetropags
    2. Hay un par de lenguajes disjuntos en NP que son inseparables a P [4];
    3. α<1norteα-ttpags
    4. metropags
    5. NP contiene un lenguaje P-bi-inmune [3];
    6. minortemimiminortemimimiminortemimi

PAGSnortePAGS

  • Estado : abierto

[1] J. Lutz y E. Mayordomo. Cook versus Karp / Levin: separando las nociones de integridad si NP no es pequeño . Theoret Comp. Sci. 164: 141-163, 1996.

[2] D. Juedez y J. Lutz. La complejidad y distribución de problemas difíciles . SIAM J. Comput 24 (2): 279-295, 1995.

[3] E. Mayordomo. Casi todos los conjuntos en tiempo exponencial son P-bi-inmunes . Theoret Comp. Sci. 136: 487-506, 1994.

[4] L. Fortnow, J. Lutz y E. Mayordomo. Inseparabilidad e hipótesis fuertes para pares NP disjuntos . En Jean-Yves Marion y Thomas Schwentick, editores, Actas del 27 ° Simposio sobre aspectos teóricos de la informática, volumen 5 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 395-404. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Alemania, 2010.

revs Joshua Grochow
fuente
Excelente. Creo que puede rastrear la suposición de la tesis doctoral de Lutz de 1987 " Categoría limitada por recursos y medida en clases de complejidad exponencial " o su documento IEEE de 1987 "Categoría de Baire limitada por recursos y pequeños circuitos en espacio exponencial" (que no está disponible en línea !).
MS Dousti
6
  • Supuesto: NEEEE .
  • Citado por primera vez en: Mihir Bellare y Shafi Goldwasser. 1994. La complejidad de la decisión frente a la búsqueda . SIAM J. Comput. 23, 1 (febrero de 1994), 97-119.
  • Uso (s): si el supuesto se cumple, existen problemas en NP cuya versión de búsqueda no (polinomialmente) Cook-reduce a su versión de decisión. En otras palabras, bajo el supuesto dado, no todos los idiomas en NP son auto reducibles .
  • Estado: abierto.
Sadeq Dousti
fuente