Razões para acreditar

27

Parece que muitas pessoas acreditam que PNPcoNP , em parte porque acreditam que o fatoramento não é passível de solvência. (Shiva Kintali listou alguns outros problemas de candidatos aqui ).

Por outro lado, Grötschel, Lovász e Schrijver escreveram que "muitas pessoas acreditam que ". Esta citação pode ser encontrada em Algoritmos Geométricos e Otimização Combinatória, e Schrijver faz afirmações semelhantes em Otimização Combinatória: Poliedros e Eficiência . Essa imagem deixa claro onde Jack Edmonds se posiciona sobre o assunto.P=NPcoNP

Que evidência apóia uma crença em ? Ou para apoiar ?P = N P c o N PPNPcoNPP=NPcoNP

Austin Buchanan
fonte
Defina "motivo". Não há realmente nenhuma evidência de uma maneira ou de outra. Isso não é algo que pode ser testado experimentalmente. Até que tenhamos uma prova maneira ou de outra, as únicas "razões para acreditar" que é sentimentos de intestino, ou que algum problema em não é polinomial, ou algum instinto que todos eles são. NPcoNP
jmite
2
Eu esperava respostas como o que Scott Aaronson deu por P contra NP .
Austin Buchanan
1
muitas das mesmas idéias aaronson são aplicáveis. discordo um pouco com jmite. há muitas evidências circunstanciais , incluindo evidências experimentais, algumas listadas por aaronson.
vzn
5
Teorema 3.1 de Permutações unidirecionais e linguagens de autocontrole C. Homan e M. Thakur, Journal of Computer and System Sciences, 67 (3): 608-622, novembro de 2003. [ as .pdf ] afirma que P ≠ UP∩ coUP se e somente se ("pior caso") existirem permutações de mão única. O teorema 3.2 lembra 10 hipóteses adicionais que se mostraram equivalentes a P P UP∩coUP.
Thomas Klimpel
9
Penso que fatorar ∈ P é muitas, muitas ordens de magnitude mais provável que P = NP ∩ coNP, de modo que essa certamente não é a razão pela qual acredito que P = NP ∩ coNP.
Peter Shor

Respostas:

5

Teorema 3.1 de Permutações unidirecionais e linguagens de autocontrole C. Homan e M. Thakur, Journal of Computer and System Sciences, 67 (3): 608-622, novembro de 2003. [ as .pdf ] afirma que se e somente se ( "pior caso") de uma via existir permutações. Teorema 3,2 recorda 10 outras hipóteses que foram mostrados para ser equivalente a P L P c o L P .PvocêPcovocêPPvocêPcovocêP

Além disso, temos forte razão para conjectura de que . Portanto, o teorema acima e o resultado conjectura em uma forte razão para acreditar que P N P C O N P .vocêPNPPNPcoNP


Isenção de responsabilidade: movi a edição de Mohammad Al-Turkistany da minha resposta para esta resposta da wiki da comunidade. Ele acredita que ele responde perfeitamente à pergunta, já que a existência de permutações unidirecionais é amplamente considerada. Eu mesmo ainda não compreendi suficientemente a diferença entre as funções unidirecionais "pior caso" e "caso médio" para afirmar que realmente responde à pergunta.

Thomas Klimpel
fonte
0

Acredito que existem geradores de números aleatórios de alta qualidade, com eficiência de espaço. Apesar dessa crença, eu normalmente uso o twister Mersenne no meu código, que é de alta qualidade, mas não economiza muito espaço. Há um vínculo ausente entre eficiência de espaço e NP∩coNP, é apenas uma sensação de que existe um link.


Deixe-me tentar dar uma das razões pelas quais acredito que a "verdadeira aleatoriedade" pode ser simulada / aproximada de um espaço muito eficiente. Sabemos que é possível produzir números pseudo-aleatórios que são suficientemente aleatórios para todos os fins práticos (incluindo criptografia). Também sabemos que usar (uma pequena quantidade de números primos fixos) grandes na construção de geradores de números pseudo-aleatórios raramente é uma má idéia. Sabemos de conjecturas como a de Riemann que quase todos os números primos contêm um alto grau de aleatoriedade, mas também sabemos que ainda não somos capazes de provar isso rigorosamente.

Existe uma explicação intuitiva por que os números primos se comportam como números aleatórios? Os números primos são o complemento dos números compostos. O complemento de um conjunto bem comportado é geralmente mais complicado que o conjunto original. Os números compostos são compostos de números primos, o que, por sua vez, já confere a esse conjunto uma certa complexidade.


Antecedentes Tentei entender uma vez por que P P NP é difícil. Gostaria de saber se a aproximação de grupos de simetria interna de uma instância do problema por grupos nilpotentes pode não levar a um "algoritmo de abstração" capaz de ver a estrutura interna da instância do problema. Mas então percebi que mesmo o cálculo da estrutura de um grupo sem potencial contém o fatoração como um caso especial. A questão dos subgrupos simples de um grupo cíclico de ordem n é equivalente à determinação dos fatores primos de n. E a classificação de grupos nilpotentes finitoscontém subproblemas ainda piores relacionados ao isomorfismo do gráfico. Isso foi suficiente para me convencer de que essa abordagem não ajudará. Mas meu próximo passo foi tentar entender por que o fatoração é difícil, e a resposta acima é o que eu vim. Foi o suficiente para me convencer, então talvez também seja convincente para outras pessoas. (Naquela época, eu não sabia sobre grupos grupóides ou semigrupos inversos, provavelmente mais adequados do que grupos sem potencial para lidar com simetrias internas. Ainda assim, o argumento por que essa abordagem não será eficiente permanece o mesmo.)

Thomas Klimpel
fonte
2
Não tenho certeza de como essa resposta está relacionada à pergunta. Você poderia elaborar?
Matthias
@ Matthias A resposta é a razão pela qual acredito que P ≠ NP∩coNP. Portanto, o problema provavelmente não é a relação com a pergunta, mas como explicar o raciocínio. Existe uma forma de platonismo matemático envolvido, que pressupõe que as estruturas matemáticas são capazes de modelar ou aproximar quase tudo o que pode existir neste mundo. A verdadeira aleatoriedade é parte do que pode existir, e a resposta tenta explicar por que há uma sensação de que essa aleatoriedade já está presente em contextos com espaço suficiente para causar P cause NP∩coNP. (Desculpe, talvez eu vai melhorar / remover este comentário mais tarde.)
Thomas Klimpel
2
@ Matthias eu escrevi "... elo perdido entre eficiência de espaço e NP∩coNP, é apenas um pressentimento ..." na resposta. Eu poderia tentar elaborar, mas temo que isso não seja bem recebido. Na verdade, acho que você prefere referências independentes apontando nessa direção, em vez de minhas próprias explicações. No Zoológico de Complexidade , descobri que o resultado citado "permutações de pior caso" existe se, e somente se, P for igual a UPUPUP [ HT03 ]. O artigo está online, mas ainda não o li ...
Thomas Klimpel 28/11