Uma antologia de pressupostos de complexidade
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ΣP2Σ2PPSAT[k]=PSAT[k+1]PSAT[k]=PSAT[k+1]PSAT[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:
Yao considera a seguinte suposição plausível: .RP⊆⋂ϵ>0DTIME(2nϵ)RP⊆⋂ϵ>0DTIME(2nϵ)
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):
A suposição em si;
O primeiro artigo em que a suposição é feita;
Resultados interessantes em que a suposição é usada;
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:
Wiki de primitivos criptográficos e problemas graves em criptografia .
Suposições criptográficas e problemas difíceis de Helger Lipmaa .
Agradável. David Johnson fez algo semelhante para resultados de complexidade usados ​​para mostrar dureza de aproximação em uma coluna recente.
@Suresh: Um link para a coluna de Johnson é muito apreciado.
— MS Dousti 08/04/11
Exigir o primeiro artigo pode ser complicado.
@ 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.
@Sadeq: www2.research.att.com/~dsj/columns/col25.pdf
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.
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.
Como Mohammad escreve, a descrição em "Uso (s)" é imprecisa ou incorreta.
@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.
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)≠0μp(NP)≠0P≠NPP≠NP
≤pT≤Tp≤pm≤mp
Há um par de linguagens disjuntas no NP que são inseparáveis ​​em P [4];
α<1α<1≤pnα−tt≤nα−ttp
≤pm≤mp
NP contém uma linguagem P-bi-imune [3];
E≠NEE≠NEEE≠NEEEE≠NEEEE≠NEEEE≠NEE
[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.
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
Suposição: NEE ≠ EE .
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 .