Uma prova assumindo uma lei física seria considerada suficiente?

8

Eu sempre me perguntei se as provas em ciência da computação seriam consideradas provas suficientes da proposição se elas precisassem assumir leis físicas?
Por exemplo, estou imaginando o que aconteceria se alguém algum dia provasse P! = NP sob a suposição da segunda lei da termodinâmica. Isso resolveria o debate de P! = NP?
Ou o problema ainda seria considerado sem solução se se basear em suposições físicas?

proofs user541686
fonte
6
A segunda lei da termodinâmica não tem nada a ver com P NP, que é uma questão puramente matemática. Isso seria essencialmente como dizer que a relatividade era necessária para uma prova do teorema de Pitágoras. ≠
Peter Shor
@ PeterShor: Não vejo o porquê, embora seja provavelmente porque não sei o suficiente para ver o porquê. Mas sinto que, intuitivamente, não ficaria completamente surpreso se houvesse uma conexão. Isso é obviamente puramente hipotético, mas se cada troca de bits tiver um aumento mínimo associado à entropia, por exemplo, talvez você possa usar a alteração de entropia da entrada para a saída para argumentar que um certo número de bits deve ter sido invertido, o que levaria uma quantidade mínima de, por exemplo, tempo exponencial. Ou algo assim, eu não sei. Essa prova está completamente fora de questão? (Por que?)
user541686
@ Kaveh: Eu não tenho um exemplo, mas eis um exemplo em potencial: acho que é razoável perguntar se um axioma como o axioma da escolha "realmente" se aplica ao mundo físico. Talvez seja, talvez não; talvez nunca tenhamos uma maneira de testá-lo. Mas certamente podemos perguntar. E se houvesse uma maneira física de provar que sim (não), isso implicaria que quaisquer teoremas baseados nele são (in) verdadeiros no mundo físico. Portanto, se eu aceito que a pergunta acima é válida, não é necessário um grande salto de fé para perguntar se existe um axioma subjacente, por exemplo, P vs. NP.
user541686
6
No seu comentário acima, acho que você está confundindo duas coisas diferentes: o uso de idéias derivadas de leis físicas em provas matemáticas e o uso das leis reais da física em provas matemáticas. Por exemplo, existem muitas provas matemáticas que usam a definição matemática de entropia; no entanto, essa definição matemática existe e é útil independentemente de as leis da termodinâmica serem verdadeiras ou não na física. Outro exemplo - podemos usar o espaço euclidiano em provas matemáticas, apesar do espaço físico real ser curvado e não euclidiano.
Peter Shor

Respostas:

7

Parece-me pelo menos possível, mas atualmente muito improvável. Para resumir o abaixo, é porque a declaração matemática atual de (digamos) P vs NP é completamente independente de qualquer lei da física, então seria necessário descrever novos modelos de computação que dependem de axiomas da física.

O ponto-chave que Peter Shor fez em seu comentário é que questões da teoria de CS, como P vs NP, se referem a modelos matemáticos muito simples e estilizados. Eles não são declarações sobre o mundo real. Eles apenas dizem "neste modelo matemático, ___ é verdadeiro".

Agora, muitas vezes temos leis empíricas, como a tese de Church-Turing, que afirmam que o mundo real age como esses modelos matemáticos. Mas essa é uma conexão unidirecional (não significa que os modelos matemáticos devem agir como o mundo real!). Para aprofundar o exemplo de Peter Shor, o teorema de Pitágoras precisa apenas das idéias de números reais e do plano / distância euclidiana. O modelo é muito mais simples que o mundo real e não envolve, por exemplo, gravidade, eletromagnetismo, termodinâmica, etc. E mesmo que o teorema de Pitágoras às vezes fosse falso na realidade por causa dessas complicações, isso não afetaria sua verdade matemática.

Da mesma forma, o modelo para a máquina de Turing e as definições de P, NP, etc, são muito mais simples que o mundo real. O modelo não envolve coisas como gravidade, entropia termodinâmica, etc. A verdade de P vs. NP não depende se a computação pode realmente acontecer eficientemente no mundo real.

Agora, parece-me hipoteticamente possível que, no futuro, possamos descobrir conexões mais próximas entre leis da física e leis da computação. O que aconteceria então é que o modelo matemático da Máquina de Turing precisaria ser expandido para dar conta dessas conexões. Seria necessário formular novas definições de P e NP para esse novo modelo e argumentar que elas são "melhores" que o antigo modelo e definições. Então, nesse novo modelo ciente da física, poderia-se ter axiomas da física usados ​​em provas. Mas isso parece muito improvável / longe de acontecer, pelo menos para mim.

usul
fonte
4
Se revisarmos modelos e mudarmos P e NP, não seria mais o que chamamos de "P vs. NP", seria uma pergunta diferente. Já sabemos que P não é igual a computar eficientemente na prática. A razão pela qual mantemos P é porque é uma simplificação útil, não que ela capture a realidade da computação na prática.
Kaveh
Para ser justo, também nem sabemos se é impossível construir uma máquina de torneamento não determinística. Ou uma máquina PostBQP. A parte estranha é que, quando provamos coisas sobre os modelos de computação que podemos criar, podemos dizer coisas sobre os modelos que alguns consideram mais "verdadeiros" porque se aplicam a coisas reais. Mas também estudamos algoritmos sem tempo de execução viável ou modelos de computação que nunca podem ser realizados na prática, porque a possibilidade de realização dos próprios modelos é ou não independente do que podemos provar sobre eles.
Phylliida 26/08/2015
5

Gosto da pergunta ... mas a resposta ainda é "não", como outros colaboradores indicaram. A questão em si é metamatemática, e é por isso que eu gosto.

Matemática e física são universos epistemológicos diferentes, e nunca os dois se encontrarão. Um universo matemático é construído de 1) definições (como os inteiros) 2) axiomas e 3) regras para contratar novas afirmações verdadeiras a partir de afirmações verdadeiras conhecidas (como Modus Ponens, que determina que A-> B e A juntos implicam B). Objetos físicos não têm entrada em tal universo.

O universo físico é matéria - e, como Schopenhauer disse, matéria é causalidade e causalidade é matéria. Objetos e provas matemáticas não têm nenhum impacto como tal no mundo físico (embora possa haver impactos de pessoas que acreditam em afirmações matemáticas e suas provas). A ciência consiste em sistemas que descrevem, mais ou menos fielmente, fenômenos observáveis ​​do mundo físico. Acho que Karl Popper capturou melhor essa epistemologia em sua teoria da falsificação empírica. A ciência utiliza a matemática em suas descrições, mas a ciência não é ela mesma o mundo fenomenal.

Os fenômenos naturais não precisam obedecer à nossa matemática, e nossa matemática não pode ser provada verdadeira ou falsa pelo mundo físico. Mas não é por acaso que a matemática parece capturar aspectos do que observamos - fizemos dessa maneira. O mundo fenomenal inspirou as definições que são o material do universo matemático.

Não é de surpreender que essa questão surja na ciência da computação, uma vez que o computador é o objeto físico final para imitar o mundo matemático .

Gara Pruesse
fonte
2

Por exemplo, estou imaginando o que aconteceria se alguém algum dia provasse P! = NP sob a suposição da segunda lei da termodinâmica.

a premissa da pergunta é orientada para a pesquisa, mas um tanto misturada / retrocedida no sentido a seguir. uma conexão profunda entre termodinâmica e complexidade de CS foi de fato demonstrada na área dos "óculos giratórios", onde o processo de orientação magnética durante o resfriamento imita de perto a transição de fase encontrada no SAT, e essa conexão continua a ser explorada e é considerada mais significativo do que meramente coincidência.

em certo sentido, a "dureza" computacional parece ser uma "explicação" ou modelo matemático básico para um processo termodinâmico fundamental. também a termodinâmica tem a proibição contra máquinas de energia perpétua, mas que também pode ser vista como uma restrição geral contra máquinas que não podem exceder certos "limites físicos de velocidade". se P! = NP, uma máquina física que resolvesse problemas de PN no tempo P não poderia existir e "desafiaria as leis da física", ou seja, na "velocidade" em que "manipula informações". mas muitos físicos estão concluindo as leis da física aparentemente se resumem à manipulação de informações. então, resumindo, é bem provável que a teoria da complexidade computacional no futuro explique melhor as leis fundamentais da termodinâmica.

mais detalhes, ver, por exemplo, esta tese de doutorado (2013):

vzn
fonte