Doria. V teria algum insight sobre por que existe a transição de fase nos problemas NP-completos?
Empiricamente, observa-se que ao se gerar aleatoriamente problemas (por exemplo, SAT), no ponto em que 50% dos problemas são satisfatíveis e 50%insatisfatíveis, há um pico no tempo médio de se atingir a decisão. É o ponto de transição de fase. Mas até hoje ninguém PROVOU que tal fenômeno precisa existir, poderia ser um efeito apenas da forma como os SAT solvers são implementados hoje em dias. É um fonômeno robusto: altera-se a implementação e os parêmetros dos problema, e o fenômeno persiste. []s 2017-08-19 17:33 GMT-03:00 Francisco Antonio Doria <[email protected]>: > Um detalhe: temos um lower bound para algoritmos exponenciais: se a > aritmética primitivo recursiva não provar P<NP, então há um algoritmo para > tais problemas cujo tempo de operação é pelo menos ~ exp (1/A), A a função > de Ackermann. (Já havia comentado isso.) > > 2017-08-19 11:30 GMT-03:00 Francisco Antonio Doria <[email protected]>: >> >> Newton e eu temos conversado bastante sobre o paper de Blum. É muito >> diferente do enfoque usado por nós, e sugerido por Kreisel. Para começar, >> trabalhamos explicitamente num sistema axiomático (usamos ZFC, em geral). >> Assim, P≠NP é expresso por uma sentença \Pi_2, que explicitamos. Tal >> sentença é demonstrável em ZFC se e somente se a função de Skolem associada >> é provadamente total. >> >> Aqui começam as complicações. Pois há uma infinidade de possíveis tais >> funções de Skolem; uma delas, pelo menos, não-computável. E esta função >> não-computável cresce, nos seus picos, mais que qualquer função recursiva >> total. E se tal função for total, ZFC não o demonstra (tente fazer uma prova >> em ZFC da totalidade da função Busy Beaver). >> >> Ademais, existem muitas questões indecidíveis afetando esses objetos. Uma >> prova de P<NP (melhor usar < que ≠, quase ilegível) deve mostrar o seguinte: >> para qualquer sequência infinita de máquinas de Turing poly, sempre haverá >> uma resposta errada a instância, digamos, de Sat, como input. Ora, podemos >> gerar algoritmicamente uma tal sequência de máquinas poly P* tal que ``P* é >> uma sequência de máquinas poly'' seja indecidível. Ou seja, haverá >> sequências infinitas de máquinas, digamos assim, numa espécie de limbo... >> >> O melhor resultado que obtivemos foi fraco. É um resultado relativo: Se >> ZFC é sound, então ZFC + ``ZFC é \Sigma_1 sound'' prova que em ZFC não >> existe demonstração de P<NP. >> >> >> 2017-08-19 10:09 GMT-03:00 Famadoria <[email protected]>: >>> >>> You 're welcome, sir! >>> >>> Sent from my iPhone >>> >>> On 19 Aug 2017, at 09:52, [email protected] wrote: >>> >>> Doria: >>> Obrigado pelo material enviado. >>> >>> NC >>> >>> Em Sáb 19/08/17 09:50, Famadoria [email protected] escreveu: >>> >>> >>> >>> Sent from my iPhone >>> >>> Begin forwarded message: >>> >>> From: Joao Marcos <[email protected]> >>> Date: 18 August 2017 04:36:18 GMT-3 >>> To: Lista acadêmica brasileira dos profissionais e estudantes da área de >>> LOGICA <[email protected]> >>> Subject: Re: [Logica-l] A Solution of the P versus NP Problem >>> Reply-To: [email protected] >>> >>> On the Edge of Eclipses and P=NP >>> >>> https://rjlipton.wordpress.com/2017/08/17/on-the-edge-of-eclipses-and-pnp/ >>> >>> E para quem quiser uma referência geral para acompanhar as discussões >>> "em tempo real": >>> >>> https://cstheory.stackexchange.com/questions/38803/is-norbert-blums-2017-proof-that-p-ne-np-correct >>> >>> >>> JM >>> >>> -- >>> Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" >>> dos Grupos do Google. >>> Para cancelar inscrição nesse grupo e parar de receber e-mails dele, >>> envie um e-mail para [email protected]. >>> Para postar neste grupo, envie um e-mail para [email protected]. >>> Visite este grupo em >>> https://groups.google.com/a/dimap.ufrn.br/group/logica-l/. >>> Para ver esta discussão na web, acesse >>> https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CAO6j_LgteuUR7%2B%3D8kOqK98Vu0zFmRvYq%2BSvnwjnD7e%2BY4zMPyg%40mail.gmail.com. >> >> >> >> >> -- >> fad >> >> ahhata alati, awienta Wilushati > > > > > -- > fad > > ahhata alati, awienta Wilushati > > -- > Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos > Grupos do Google. > Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie > um e-mail para [email protected]. > Para postar nesse grupo, envie um e-mail para [email protected]. > Acesse esse grupo em > https://groups.google.com/a/dimap.ufrn.br/group/logica-l/. > Para ver essa discussão na Web, acesse > https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CA%2BuR7BKxOtg59_ZApgv2U%2BEzJ14mEuQOvvmu3RE8B0MJ9%3Dxrbg%40mail.gmail.com. -- Marcelo Finger Departament of Computer Science, IME University of Sao Paulo http://www.ime.usp.br/~mfinger -- Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google. Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para [email protected]. Para postar neste grupo, envie um e-mail para [email protected]. Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/. Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CABqmzx04-Lwx6f6prmFp8OSPOBGD4yffe3xdY8nh9ASTXs6Q0A%40mail.gmail.com.
