[Logica-l] el problema

2017-05-22 Por tôpico Joao Marcos
El problema que los informáticos no han podido resolver en 45 años - La pregunta "¿P=NP?" trae de cabeza a los programadores desde 1971 por Ricardo Peña Marí (Universidad Complutense de Madrid) http://tecnologia.elpais.com/tecnologia/2017/05/19/actualidad/1495202801_698394.html -- Você está receb

Re: [Logica-l] el problema

2017-05-22 Por tôpico Thiago Nascimento da Silva
O texto diz que se P = NP, então teríamos encontrado algoritmos, no caso existe, encontrar é outro trabalho. Em 22 de maio de 2017 18:18, Joao Marcos escreveu: > El problema que los informáticos no han podido resolver en 45 años > - La pregunta "¿P=NP?" trae de cabeza a los programadores desde 1

Re: [Logica-l] el problema

2017-05-22 Por tôpico Claus Akira Horodynski Matsushigue
Pois é! Esta é uma pergunta (?) interessante!!! Se a solução do problema for (fosse) um EXISTE CLÁSSICO um algoritmo/programa (i.e., existe exclusivamente da Lógica Clássica), certamente seria interessante, mas não serviria em nada prá esta questão prática que é da Computação. Prá Computação, fa

Re: [Logica-l] el problema

2017-05-22 Por tôpico Famadoria
Tem casos em que a gente pode provar que há um algoritmo sem exibi-lo. Sent from my iPhone > On 22 May 2017, at 21:15, Claus Akira Horodynski Matsushigue > wrote: > > > Pois é! Esta é uma pergunta (?) interessante!!! > > Se a solução do problema for (fosse) um EXISTE CLÁSSICO um algoritmo/

Re: [Logica-l] el problema

2017-05-22 Por tôpico Marcelo Finger
2017-05-22 22:00 GMT-03:00 Famadoria : > Tem casos em que a gente pode provar que há um algoritmo sem exibi-lo. Certamente. Basta mostrar que um problema é NP-completo que segue que há uma redução polinomial para qualquer outro problema NP-completo. Encontrar estas reduções são outros 500. []s

Re: [Logica-l] el problema

2017-05-22 Por tôpico Famadoria
Preciso. Sent from my iPhone > On 22 May 2017, at 22:39, Marcelo Finger wrote: > > 2017-05-22 22:00 GMT-03:00 Famadoria : >> Tem casos em que a gente pode provar que há um algoritmo sem exibi-lo. > > Certamente. Basta mostrar que um problema é NP-completo que segue que > há uma redução polin

Re: [Logica-l] el problema

2017-05-22 Por tôpico Famadoria
E tem coisa mais estranha aí. Sent from my iPhone > On 22 May 2017, at 22:39, Marcelo Finger wrote: > > 2017-05-22 22:00 GMT-03:00 Famadoria : >> Tem casos em que a gente pode provar que há um algoritmo sem exibi-lo. > > Certamente. Basta mostrar que um problema é NP-completo que segue que

Re: [Logica-l] el problema

2017-05-22 Por tôpico 'Samuel Gomes' via LOGICA-L
Prezados, Aproveito para apresentar uma pergunta que anda pela minha cabeça nos últimos dias. --> Existiria algum interesse para a Computação se algum desses problemas sobre Complexidade fosse, digamos assim, internalizado em ZF e mostrado ser uma equivalência ou uma consequência de algum prin

Re: [Logica-l] el problema

2017-05-22 Por tôpico 'Samuel Gomes' via LOGICA-L
https://cstheory.stackexchange.com/questions/1923/which-interesting-theorems-in-tcs-rely-on-the-axiom-of-choice-or-alternatively (esse é o post ao qual me referi) -- Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google. Para cancelar inscrição nesse gru

Re: [Logica-l] el problema

2017-05-22 Por tôpico Joao Marcos
Esta parte também não convence: "En cambio, si fuera P=NP, habríamos encontrado algoritmos polinomiales para todos esos problemas. La parte buena de ello es que podríamos resolver, en tiempos muy cortos, problemas del viajante con miles de ciudades y otros cientos de problemas útiles para los que