Deveríamos considerar uma lei da natureza?

30

Muitos especialistas acreditam que a conjectura é verdadeira e a usa em seus resultados. Minha preocupação é que a complexidade dependa fortemente da conjectura .PN PPNPPNP

Então, minha pergunta é:

Desde que a conjectura não seja comprovada, alguém deve / deve considerá-la como uma lei da natureza, conforme indicado na citação de Strassen? Ou devemos tratá-lo como uma conjectura matemática que talvez seja provada ou refutada algum dia?PNP

Citar:

"A evidência a favor das hipóteses de Cook e Valiant é tão avassaladora, e as conseqüências de seu fracasso são tão grotescas que seu status talvez possa ser comparado ao das leis físicas e não às conjecturas matemáticas comuns".

[Volker Strassen é laudation ao ganhador do Prêmio Nevanlinna, Leslie G. Valar, em 1986]

Eu faço essa pergunta ao ler os resultados da publicação Física no TCS? . Talvez seja interessante notar que a complexidade computacional tem algumas semelhanças com a física (teórica): muitos resultados importantes da complexidade foram provados assumindo , enquanto que nos resultados físicos teóricos são provados assumindo algumas leis físicasPNP P N P E=m c 2 . Nesse sentido, pode ser considerado algo como . Voltar aos resultados de Física em TCS? :PNPE=mc2

Poderia (parte do) TCS ser um ramo das ciências naturais?

Esclarecimento:

(veja a resposta de Suresh abaixo)

É legítimo dizer que a conjectura na teoria da complexidade é tão fundamental quanto as leis físicas da física teórica (como disse Strassen)?PNP

vb le
fonte
10
O site cstheory.stackexchange.com não é um local adequado para discussões. Por favor, verifique “Que tipo de perguntas não devo fazer aqui?” Nas Perguntas frequentes .
Tsuyoshi Ito 27/01
11
Bem, espero que alguém possa ter a resposta certa para minha pergunta. Acho que o ponto de vista de Strassen é bastante interessante e, curiosamente, não conversamos sobre isso. Vou verificar o FAQ agora ...
vb le
8
Você está pedindo a opinião das pessoas, não os fatos, portanto essa pergunta é claramente inadequada na minha opinião. Você não precisa concordar, mas espero que minha posição seja clara.
Tsuyoshi Ito 27/01
30
Penso que esta questão é bastante importante e que, neste caso, podemos abrir uma exceção à tendência de evitar discussões.
Gil Kalai
3
Gil Kalai: Há muitas coisas importantes a serem discutidas neste mundo, mas cstheory.stackexchange.com não é o lugar certo para elas. Por favor, discuta-os em outro lugar.
Tsuyoshi Ito

Respostas:

57

A declaração de Strassen precisa ser contextualizada. Este foi um discurso para um público de matemáticos em 1986, época em que muitos matemáticos não tinham uma opinião alta da ciência da computação teórica. A declaração completa é

Para alguns de vocês, pode parecer que as teorias discutidas aqui se apóiam em bases fracas. Eles não. A evidência a favor das hipóteses de Cook e Valiant é tão avassaladora, e as conseqüências de seu fracasso são tão grotescas que seu status talvez possa ser comparado ao das leis físicas e não às conjecturas matemáticas comuns.

Tenho certeza de que Strassen teve conversas com matemáticos puros que disseram algo ao longo das linhas de

"Você está baseando toda a teoria da complexidade em um castelo de cartas. E se P = NP? Então todos os seus teoremas não terão sentido. Por que você não faz um pouco de esforço e prova que P NP, em vez do que continuar construindo uma teoria sobre fundações tão fracas ".

Em 2013, quando P NP é um problema do prêmio Clay há uma dúzia de anos, pode parecer difícil acreditar que algum matemático realmente tenha essas atitudes; no entanto, posso garantir pessoalmente que alguns o fizeram.

Strassen continua dizendo que não devemos desistir de procurar uma prova de P NP (implicando indiretamente que é de fato uma conjectura matemática):

No entanto, uma prova tradicional seria de grande interesse, e me parece que a hipótese de Valiant pode ser mais fácil de confirmar do que a de Cook ...

então talvez eu o rotulei como uma "hipótese de trabalho" em vez de uma "lei física".

Finalmente, note que os matemáticos também usam tais hipóteses de trabalho. Há um grande número de trabalhos de matemática que provam teoremas cujas afirmações correm "Supondo que a hipótese de Riemann seja verdadeira, então ...".

Peter Shor
fonte
11
"Por que você não colocar diante de um pouco de esforço e provar que P NP ..." - mas provavelmente enorme esforço tem sido colocado fwd desde o início da conjectura ....
vzn
7
@vzn: é por isso que os matemáticos que disseram coisas assim eram tão irritantes.
Peter Shor
ok, sim, concordou que os matemáticos, talvez um pouco injustos, não reconheceram P NP como matematicamente significativo ou possivelmente fundamental até possivelmente décadas depois do início do processo e o prêmio Clay provavelmente teve muito a ver com ajudar aquele. um interessante estudo de caso próximo disso é a redação de Gowers [medalhista de campo ] da prova de limites inferiores do circuito monótono de Razborov . e, claro, a conjectura de Riemann é outro problema de matemática argila .... juntamente com outros principalmente os de matemática ...=?
vzn
20

Eu posso ver três maneiras relacionadas de entender a pergunta:

1) Podemos considerar como um princípio fundamental da teoria da complexidade computacional, mesmo antes de podermos provar isso?NPP

2) O princípio se estende além de seu estreito significado matemático?NPP

3) O princípio pode ser considerado uma lei física.NPP

Penso que existem boas razões para responder 'sim' ou 'sim qualificado' para todas essas três perguntas.

Gil Kalai
fonte
11

Eu não tenho certeza se entendi. Uma lei física (do tipo que você indica) é uma expressão matemática de um modelo (nesse exemplo, a relatividade) que afirma capturar a realidade. Pode-se provar que uma lei física está errada se a matemática subjacente estiver incorreta, mas também pode estar errada se o modelo subjacente mudar (por exemplo, mecânica newtoniana). P vs NP é uma conjectura matemática específica que é verdadeira ou falsa (e pode ser provável ou não)

Suresh Venkat
fonte
Sei que exagerei na citação de Strassen. Minha preocupação é que a complexidade dependa fortemente da questão P vs NP, como a física em suas leis (como você esclareceu). Portanto, a pergunta é: enquanto a conjetura P vs. NP não for comprovada, alguém deve / deve considerá-la como uma lei física, como indicado Strassen?
vb le
7

Para responder à sua pergunta original:

Sim, pelo menos Scott Aaronson acredita que é uma lei da natureza. Ele propôs a seguinte formulaçãoPNP

"A suposição de dureza NP ?: Não há meios físicos para resolver problemas completos de NP em tempo polinomial".

Ele deu uma boa palestra na Universidade de Waterloo intitulada Intratabilidade computacional como uma lei da física

Mohammad Al-Turkistany
fonte
13
7
+1. De uma das conversas que tive com um amigo, acabei acreditando que o universo não teria razão de existir se P = NP.
labotsirc
2
@labotsirc você poderia dar suas razões?
T ....
5

NLPSPACENPcoNPPNP

T ....
fonte
Do ponto de vista matemático, sua resposta faz sentido, mas a pergunta não é matemática. Eu acho que P vs. NP é uma questão mais natural e intuitiva, por isso não é razoável pensar que P vs. NP é mais adequado como ponto de partida. No fundo, acho que a questão não é matemática, mas como os modelos matemáticos de computação que construímos correspondem ao mundo real e o que pode ser feito nele.
Kaveh
11
NPcoNPPNP
1

ϕϕ

Thinniyam Srinivasan Ramanatha
fonte
8
Exceto que sabemos que, se as leis físicas não impedissem a criação de máquinas Blum-Shub-Smale em nosso universo, P e NP seriam equivalentes. Portanto, a questão está relacionada ao mundo físico nesse sentido.
Kyle Jones
@ KyleJones Desculpe, eu não entendo o que você está dizendo (provavelmente porque eu não sei o suficiente sobre o modelo BSS). Você poderia me dar uma referência que explica isso com mais detalhes?
Thinniyam Srinivasan Ramanatha
Eu quis dizer que, se uma prova matemática da declaração for produzida, nenhuma evidência do mundo físico poderá refutá-la.
Thinniyam Srinivasan Ramanatha
-4

Você pode fazer muitos experimentos sobre velocidades e velocidades e obterá evidências esmagadoras para validar as leis de Newton. Obviamente, você verá coisas muito estranhas em experimentos muito particulares, como a velocidade da luz na água em movimento ou alguns eventos astronômicos. Mas suas evidências esmagadoras lhe dirão: Newton está certo e essas leis são o que você precisa

É claro que Newton "não está certo", e Einstein veio atrás dele.

Para P = NP, podemos ver muitos exemplos em que parece P ≠ NP. Mas, em alguns casos particulares, temos coisas estranhas. Se P ≠ NP, há um número infinito de classes entre elas, portanto, devemos encontrar alguns problemas no NP que não estão no P, mas não estão completos no NP. Não conhecemos nenhum deles, e a maioria dos candidatos provou estar em P.

O que você pensa sobre esse problema depende de onde você deseja olhar. Eu não ficaria surpreso se P = NP.

Xoff
fonte
7
Na verdade, ainda há muitos candidatos para problemas NP-intermediários, cuja complexidade exata permanece sem solução: cstheory.stackexchange.com/questions/79/...
Joshua Grochow
é bom saber esta lista, obrigado por este comentário!
Xoff 28/01