A solução do problema P versus NP (Balela ou história sendo vista ao vivo)

[gekinganger]

Esse é o artigo que garante isso: https://arxiv.org/pdf/1708.03486.pdf
Será mais um artigo fake ou algo que resolver a dúvida de 1 milhão de doláres?

Então quanto será que estão as odds da descoberta, será q vão pagar mesmo ou vão descobrir que é falho?

Muita gente acha que vão achar falha no artigo. E vcs?

AVISO: TÓPICO ANTIGO Atenção: Este é um tópico criado há mais de 90 dias. Caso não tenha respostas recentes, tenha certeza de que sua resposta é conveniente e útil o suficiente para reativar esta discussão, do contrário você poderá ser advertido/suspenso.

[madru]

To com preguiça de ler td isso.
Eles provam que P != NP? Pq se for P = NP já beto que vai falhar..

Sent from my ASUS_Z00AD using Tapatalk

[gekinganger]

P != np
mas já apareceram trocentos artigos "provando" mas que não provaram nada.

[rbmrenato]

E se conseguir provar, vale bem mais que 1kk usd.

[VinnyCout]

so, wtf is that?

[FrAAnKK Jr]

Basicamente: P é o nome dado em ciencia da computação a todo problema que dado uma entrada de tamanho n, você consegue resolver ela de forma polinomial em razão ao tamanho da entrada, ou seja como uma função de tempo linear em relação a n.

NP são os problemas em que a solução não consegue ser dada de forma polinomial, ou seja, dada uma entrada de tamanho n, a solução do problema vai levar um tempo exponencial, por exemplo. Com isso quanto maior o n maior o tempo para a resolução. Geralmente os problemas de criptografia estão em sua maioria nesse conjunto, o que faz com que sejam "impossíveis" de serem quebrados, pois levariam de milhares de anos ao infinito para serem resolvidos tendo uma entrada de tamanho razoável.

Por exemplo um problema NP de quebra de uma chave criptográfica que demore exponencialmente 10 segundos para cada bit de uma entrada n. Para a solução de uma chave de 1 bit (ou seja n=1) seria 10 elevado a n, ou seja 10 segundos. Para uma entrada de uma chave de tamanho 256 (usadas em criptografias comuns hoje em dia), teríamos 10 elevado a 256, que é absurdamente maior que a existência do universo.

A grande questão em computação é saber se é possível que esses problemas NP possam ser resolvidos por algum método que "transforme" eles em um problema P. Ou seja, em tempo linear. Por exemplo se esse problema de quebra de criptografia fosse possível ser resolvido por uma solução que ao invés de 10 eleveado a n, pudéssemos ter 10 vezes n. Logo para 1 bit, teríamos 10 segundos, e para 256 bits teríamos 10 x 256 = 2560 segundos ou seja seria factível quebrar essa criptografia.

BEM basicamente, essa é a questão P vs NP. Entendível?

[FrAAnKK Jr]

A grande questão é que ninguém até hoje provou nem que isso é possível, e nem que é impossível. E esse é um dos problemas em que o MIT oferece U$ 1 milhão de dólares pela solução.

Provar que é impossível (como o artigo fez) garantiria que toda a criptografia existente nunca seria violada dentro dos poderes computacionais existentes.

[Ljc]

"Basicamente: P é o nome dado em ciencia da computação a todo problema que dado uma entrada de tamanho n, você consegue resolver ela de forma polinomial em razão ao tamanho da entrada, ou seja como uma função de tempo linear em relação a n.

NP são os problemas em que a solução não consegue ser dada de forma polinomial, ou seja, dada uma entrada de tamanho n, a solução do problema vai levar um tempo exponencial, por exemplo. Com isso quanto maior o n maior o tempo para a resolução. Geralmente os problemas de criptografia estão em sua maioria nesse conjunto, o que faz com que sejam "impossíveis" de serem quebrados, pois levariam de milhares de anos ao infinito para serem resolvidos tendo uma entrada de tamanho razoável.

Por exemplo um problema NP de quebra de uma chave criptográfica que demore exponencialmente 10 segundos para cada bit de uma entrada n. Para a solução de uma chave de 1 bit (ou seja n=1) seria 10 elevado a n, ou seja 10 segundos. Para uma entrada de uma chave de tamanho 256 (usadas em criptografias comuns hoje em dia), teríamos 10 elevado a 256, que é absurdamente maior que a existência do universo.

A grande questão em computação é saber se é possível que esses problemas NP possam ser resolvidos por algum método que "transforme" eles em um problema P. Ou seja, em tempo linear. Por exemplo se esse problema de quebra de criptografia fosse possível ser resolvido por uma solução que ao invés de 10 eleveado a n, pudéssemos ter 10 vezes n. Logo para 1 bit, teríamos 10 segundos, e para 256 bits teríamos 10 x 256 = 2560 segundos ou seja seria factível quebrar essa criptografia."

BEM basicamente, essa é a questão P vs NP. Entendível?

Totalmente entendível. Muito obrigado pela explicação!