O que aconteceria se fosse provado que P = NP? [RESOLVIDO]

1. O que aconteceria se fosse provado que P = NP? [RESOLVIDO]

Samuel Leonardo
SamL

(usa XUbuntu)

Enviado em 26/05/2017 - 09:10h

E aí, o que pode acontecer se os problemas mais difíceis forem faceis de resolver num tempo polinomial? Alguém pode me dar uma perspectiva?


  


2. MELHOR RESPOSTA

Buckminster
Buckminster

(usa Debian)

Enviado em 26/05/2017 - 23:31h

Bom, o problema do caixeiro viajante é um exemplo clássico de problema de otimização combinatória. A coisa básica, entre outras, a ser pensada nesse problema é reduzi-lo a um problema de enumeração. Acha-se todas as rotas possíveis e calcula-se o comprimento de cada uma delas para ver qual a menor rota.
Seguindo nessa estratégia reducionista, podemos calcular o comprimento total de cada rota e ver qual delas tem o menor comprimento total, o que seria uma tarefa fácil para um computador, porém, na prática não é o que acontece, pois o computador teria que ter uma memória ilimitada e irrestrita uma vez que aumentando-se o número de cidades o número do fatorial também aumenta.
Veja aqui: http://www.mat.ufrgs.br/~portosil/caixeiro.html

No link acima vemos que o método reducionista não é prático (a não ser para o caso de poucas cidades). E costuma-se resumir essas propriedades do problema do caixeiro viajante dizendo que ele pertence à categoria dos problemas NP-completos.
A dificuldade de fatoração é de uma natureza diferente dos outros problemas de busca difíceis. Por exemplo, ninguém acredita que fatoração seja um NP-completo. Mas tem algumas exceções.
Veja: http://www.inf.ufpr.br/vignatti/courses/ci165/23.pdf

Poderíamos partir do princípio que uma redução em tempo polinomial é uma redução que é computável por uma Máquina de Turing determinística em tempo polinomial onde a classe de complexidade P é o conjunto dos problemas de decisão que são solúveis em tempo polinomial.
E um problema pertence à classe NP se e somente se ele puder ser decidido em tempo polinomial por alguma Máquina de Turing não determinística. E um problema pertence à classe NP se ele puder ser verificado em tempo polinomial (por uma Máquina de Turing determinística).
Afirmando-se que todos os problemas de complexidade P são também de complexidade NP, mas o inverso "parece" não ser verdade, porém, não se pode afirmar isso com certeza, vemos que alguns problemas "parecem" não ter soluções passíveis de serem obtidas em tempo polinomial. E esse é todo o X da questão.

Entretanto, os algoritmos podem simplesmente ainda não serem conhecidos!
Veja: http://sites.poli.usp.br/p/fabio.cozman/Didatico/Comp/Material/Turing.pdf

Um algoritmo é eficiente se ele é de complexidade polinomial no tamanho da entrada.
Vemos aqui http://www.inf.ufg.br/~diane/PAA/2006/AULA2006/VerificacaoPolinomial.pdf que o grande questionamento é justamente esse: P = NP???

Não sei se ajudei ou compliquei mais ainda, procurei citar os links como uma base de partir para os estudos, mas o grande problema é justamente se P = NP, pois NP engloba P, mas P não engloba NP.
Caso fosse provado que P=NP, como o listeiro_037 disse, nasceriam novas classes de algoritmos, e essas classes seriam a Pedra Filosofal dos algoritmos computacionais.

Não gosto muito de citar a Wikipédia, mas no link abaixo tem uma explicação com propriedade do problema:
https://pt.wikipedia.org/wiki/P_versus_NP
E aqui: http://paginas.fe.up.pt/~rossetti/rrwiki/lib/exe/fetch.php?media=teaching:1011:cal:16_1.16_2.npcompl...

Eu matutei um tempo em cima desse problema, isso em tempos antanhos, mas o problema é justamente que NP engloba P, mas P não engloba NP.
Minha sugestão é que você teria que criar outra linha de pensamento e a base disso, o começo seria estudar a Máquina de Turing a fundo.

3. Re: O que aconteceria se fosse provado que P = NP? [RESOLVIDO]

4. Re: O que aconteceria se fosse provado que P = NP?

Perfil removido
removido

(usa Nenhuma)

Enviado em 26/05/2017 - 18:23h

Nasceriam novas classes de algoritmos como aconteceu com o AKSL.
Agora, unificar todos em uma superclasse, é mais difícil.

----------------------------------------------------------------------------------------------------------------
Nem direita, nem esquerda. Quando se trata de corrupção o Brasil é ambidestro.
(anônimo)

Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it. — Edward Snowden



5. Re: O que aconteceria se fosse provado que P = NP? [RESOLVIDO]

Patrick
Freud_Tux

(usa Outra)

Enviado em 26/05/2017 - 18:36h

Interessante as linhas de lógica...

T+

-------------------------------------------------------------------------------------------------------------------------------------------------
Noob: "[...]Sou muito noob ainda usando o terminal, então preciso de ajuda "mastigada", pra operá-lo."
zhushazang: "Sou velho e meus dentes desgastados. Estude linux www.guiafoca.org";


6. Re: O que aconteceria se fosse provado que P = NP? [RESOLVIDO]

Buckminster
Buckminster

(usa Debian)

Enviado em 27/05/2017 - 21:36h

SamL escreveu:

Buckminster, obrigado por ter tirado essas dúvidas, foi de grande ajuda seu comentário. Vou baixar e acessar cada link que deixou ai, esse assunto é bom demais.
Obrigado


De nada.


7. Re: O que aconteceria se fosse provado que P = NP? [RESOLVIDO]

Moises Viana Felipe
viana3

(usa openSUSE)

Enviado em 28/05/2017 - 09:45h

Buckminster escreveu:

Bom, o problema do caixeiro viajante é um exemplo clássico de problema de otimização combinatória. A coisa básica, entre outras, a ser pensada nesse problema é reduzi-lo a um problema de enumeração. Acha-se todas as rotas possíveis e calcula-se o comprimento de cada uma delas para ver qual a menor rota.
Seguindo nessa estratégia reducionista, podemos calcular o comprimento total de cada rota e ver qual delas tem o menor comprimento total, o que seria uma tarefa fácil para um computador, porém, na prática não é o que acontece, pois o computador teria que ter uma memória ilimitada e irrestrita uma vez que aumentando-se o número de cidades o número do fatorial também aumenta.
Veja aqui: http://www.mat.ufrgs.br/~portosil/caixeiro.html

No link acima vemos que o método reducionista não é prático (a não ser para o caso de poucas cidades). E costuma-se resumir essas propriedades do problema do caixeiro viajante dizendo que ele pertence à categoria dos problemas NP-completos.
A dificuldade de fatoração é de uma natureza diferente dos outros problemas de busca difíceis. Por exemplo, ninguém acredita que fatoração seja um NP-completo. Mas tem algumas exceções.
Veja: http://www.inf.ufpr.br/vignatti/courses/ci165/23.pdf

Poderíamos partir do princípio que uma redução em tempo polinomial é uma redução que é computável por uma Máquina de Turing determinística em tempo polinomial onde a classe de complexidade P é o conjunto dos problemas de decisão que são solúveis em tempo polinomial.
E um problema pertence à classe NP se e somente se ele puder ser decidido em tempo polinomial por alguma Máquina de Turing não determinística. E um problema pertence à classe NP se ele puder ser verificado em tempo polinomial (por uma Máquina de Turing determinística).
Afirmando-se que todos os problemas de complexidade P são também de complexidade NP, mas o inverso "parece" não ser verdade, porém, não se pode afirmar isso com certeza, vemos que alguns problemas "parecem" não ter soluções passíveis de serem obtidas em tempo polinomial. E esse é todo o X da questão.

Entretanto, os algoritmos podem simplesmente ainda não serem conhecidos!
Veja: http://sites.poli.usp.br/p/fabio.cozman/Didatico/Comp/Material/Turing.pdf

Um algoritmo é eficiente se ele é de complexidade polinomial no tamanho da entrada.
Vemos aqui http://www.inf.ufg.br/~diane/PAA/2006/AULA2006/VerificacaoPolinomial.pdf que o grande questionamento é justamente esse: P = NP???

Não sei se ajudei ou compliquei mais ainda, procurei citar os links como uma base de partir para os estudos, mas o grande problema é justamente se P = NP, pois NP engloba P, mas P não engloba NP.
Caso fosse provado que P=NP, como o listeiro_037 disse, nasceriam novas classes de algoritmos, e essas classes seriam a Pedra Filosofal dos algoritmos computacionais.

Não gosto muito de citar a Wikipédia, mas no link abaixo tem uma explicação com propriedade do problema:
https://pt.wikipedia.org/wiki/P_versus_NP
E aqui: http://paginas.fe.up.pt/~rossetti/rrwiki/lib/exe/fetch.php?media=teaching:1011:cal:16_1.16_2.npcompl...

Eu matutei um tempo em cima desse problema, isso em tempos antanhos, mas o problema é justamente que NP engloba P, mas P não engloba NP.
Minha sugestão é que você teria que criar outra linha de pensamento e a base disso, o começo seria estudar a Máquina de Turing a fundo.


Talvez ao invés de focar em um estudo da máquina de Turing, seria buscar uma prova Matemática de que P é diferente de NP.



8. Re: O que aconteceria se fosse provado que P = NP? [RESOLVIDO]

Buckminster
Buckminster

(usa Debian)

Enviado em 28/05/2017 - 11:16h

"Talvez ao invés de focar em um estudo da máquina de Turing, seria buscar uma prova Matemática de que P é diferente de NP. "

viana3, essa é uma perspectiva interessante também, que decorreria naturalmente com os estudos: a prova matemática; mas não que P é diferente de NP, pois isso já está provado, ele teria que provar que P=NP.


9. Re: O que aconteceria se fosse provado que P = NP? [RESOLVIDO]

Moises Viana Felipe
viana3

(usa openSUSE)

Enviado em 28/05/2017 - 14:47h

Buckminster escreveu:

"Talvez ao invés de focar em um estudo da máquina de Turing, seria buscar uma prova Matemática de que P é diferente de NP. "

viana3, essa é uma perspectiva interessante também, que decorreria naturalmente com os estudos: a prova matemática; mas não que P é diferente de NP, pois isso já está provado, ele teria que provar que P=NP.


Mencionei o fato de que seria interessante provar que P é diferente de NP, por que no pdf citado anteriormente, diz que "Os matemáticos acreditam que P é diferente de NP", levando-me a concluir que não havia sido provado ainda.






Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts