Uma antologia de pressupostos de complexidade

32

No artigo A hipótese aleatória do Oracle é falsa , os autores (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan e Rohatgi) discutem as implicações da hipótese do oráculo aleatório . Eles argumentam que sabemos muito pouco sobre separações entre classes de complexidade, e a maioria dos resultados envolve o uso de suposições razoáveis ou a hipótese do oráculo aleatório. A suposição mais importante e amplamente aceita é que a HP não entra em colapso. Nas suas palavras:

Em uma abordagem, assumimos como hipótese de trabalho que a HP tem infinitos níveis. Assim, qualquer suposição que implique que o PH seja finito é considerada incorreta. Por exemplo, Karp e Lipton mostraram que, se NP ⊆ P / poli, o PH cai para . Portanto, acreditamos que o SAT não possui circuitos polinomiais. Da mesma forma, acreditamos que os conjuntos completos de Turing e muitos para o NP não são escassos, porque Mahaney mostrou que essas condições colapsariam o PH. Pode-se até mostrar que para qualquer k ≥ 0, implica que PH é finito. Portanto, acreditamos queΣ2PPSAT[k]=PSAT[k+1]PSAT[k]PSAT[k+1] para todos k ≥ 0. Assim, se a hierarquia polinomial é realmente infinita, podemos descrever muitos aspectos da complexidade computacional de NP.

Além da suposição de que o PH não entra em colapso, existem muitas outras suposições de complexidade. Por exemplo:

  1. Yao considera a seguinte suposição plausível: .RPϵ>0DTIME(2nϵ)
  2. Nisan e Wigderson fazem várias suposições relacionadas à derandomização.

A idéia principal dessa pergunta é o que seu título diz: Ser uma antologia de pressupostos teóricos da complexidade. Seria ótimo se as seguintes convenções fossem respeitadas (sempre que possível):

  1. A suposição em si;
  2. O primeiro artigo em que a suposição é feita;
  3. Resultados interessantes em que a suposição é usada;
  4. Se o pressuposto já foi refutado / provado, ou se sua plausibilidade já foi discutida.

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): algumas suposições criptográficas e informações sobre elas estão listadas nos seguintes sites:

  1. Wiki de primitivos criptográficos e problemas graves em criptografia .
  2. Suposições criptográficas e problemas difíceis de Helger Lipmaa .
Sadeq Dousti
fonte
2
Agradável. David Johnson fez algo semelhante para resultados de complexidade usados ​​para mostrar dureza de aproximação em uma coluna recente.
Suresh Venkat
@Suresh: Um link para a coluna de Johnson é muito apreciado.
MS Dousti 08/04/11
Exigir o primeiro artigo pode ser complicado.
András Salamon
@ András: Sim. Por esse motivo, adicionei a frase "sempre que possível". Você pode citar o artigo que considera o primeiro. Como esse é o CW, se alguém conhece um resultado mais antigo, ele simplesmente corrige o post.
MS Dousti

Respostas:

10
  • Suposição: hipótese de tempo exponencial .
  • Citado pela primeira vez em: Enquanto folclore, foi formalizado pela primeira vez no seguinte artigo: Russell Impagliazzo e Ramamohan Paturi. 1999. A complexidade do k-SAT . Em Anais da Décima Quarta Conferência Anual do IEEE sobre Complexidade Computacional ( COCO '99 ). IEEE Computer Society, Washington, DC, EUA, 237-240.
  • Utilizações: Supõe que nenhum problema de NP completo pode ser decidido em tempo subexponencial e, portanto, implica que P ≠ NP.
  • Status: aberto.
Incrível
fonte
Eu acho que a ETH assume que o problema 3-SAT não pode ser decidido em tempo subexponencial. As respostas a esta publicação ( cstheory.stackexchange.com/questions/3620/… ) implicam a existência de algoritmos de tempo subexponenciais para alguns problemas de NP-completos, como o Conjunto Independente Planar.
Mohammad Al-Turkistany
Como Mohammad escreve, a descrição em "Uso (s)" é imprecisa ou incorreta.
Yoshio Okamoto
@YoshioOkamoto: Esta é uma publicação da comunidade. Por que não seguir adiante e tornar a publicação precisa, ou até corrigi-la?
MS Dousti 2/11/11
Não tenho certeza. A página da wikipedia vinculada contém mais informações, e minha edição seria apenas uma repetição.
Yoshio Okamoto
8
  • Suposição : NP não possui p-medida 0
  • Primeiro citado em : Jack H. Lutz. Categoria e medida em classes de complexidade . SIAM J. Comput. 19: 1100-1131, 1990.
  • μp(NP)0PNP
    1. Tpmp
    2. Há um par de linguagens disjuntas no NP que são inseparáveis ​​em P [4];
    3. α<1nαttp
    4. mp
    5. NP contém uma linguagem P-bi-imune [3];
    6. ENEEENEEEENEE

PNP

  • Status : Aberto

[1] J. Lutz e E. Mayordomo. Cook versus Karp / Levin: separando noções de completude se NP não for pequeno . Theoret. Comp. Sci. 164: 141-163, 1996.

[2] D. Juedez e J. Lutz. A complexidade e distribuição de problemas difíceis . SIAM J. Comput 24 (2): 279-295, 1995.

[3] E. Mayordomo. Quase todo conjunto no tempo exponencial é imune a P-bi . Theoret. Comp. Sci. 136: 487-506, 1994.

[4] L. Fortnow, J. Lutz e E. Mayordomo. Inseparabilidade e fortes hipóteses para pares de pares disjuntos . Em Jean-Yves Marion e Thomas Schwentick, editores, Anais do 27º Simpósio de Aspectos Teóricos da Ciência da Computação, volume 5 do Leibniz International Proceedings in Informatics (LIPIcs), páginas 395-404. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Alemanha, 2010.

Joshua Grochow
fonte
Excelente. Acredito que você possa rastrear o pressuposto da tese de doutorado de Lutz, de 1987, " Categoria e Medida Limitadas por Recursos em Classes de Complexidade Exponencial " ou de seu artigo do IEEE de 1987 "categoria Baire e pequenos circuitos no espaço exponencial" (que não está disponível on-line). !).
MS Dousti 17/04/11
6
  • Suposição: NEEEE .
  • Primeiro citado em: Mihir Bellare e Shafi Goldwasser. 1994. A complexidade da decisão versus a pesquisa . SIAM J. Comput. 23, 1 (fevereiro de 1994), 97-119.
  • Uso (s): Se a suposição persistir, existem problemas no NP cuja versão de pesquisa não reduz (polinomialmente) o Cook à sua versão de decisão. Em outras palavras, sob a suposição dada, nem todos os idiomas no NP são auto-redutíveis .
  • Status: aberto.
Sadeq Dousti
fonte