Oi, Marcelo, Nunca pensei a respeito; vc teria à mão alguma referência?
O que sei é o seguinte: o problema típico de Sat é resolvido em tempo polinomial pelo algoritmo T das tabelas verdade, isso mesmo. É gozado: alta complexidade de Kolmogorov-Chaitin corresponde a baixa complexidade computacional. São expressões de Sat de baixa complexidade KC as que dão galho e demoram a serem `resolvidas'. Chaitin sabia disso, mas não sei de nenhuma referência. Num contexto mais amplo, acho que a indecidibilidade que apontei mostra por que esse problema é tão complicado: de repente o sistema axiomático onde estamos não ``vê'' o algoritmo polinomial que faz o milagre de resolver tudo em tempo polinomial... Por isso nos interessou aquele resultado parcial, relativo, que mencionei. A condição que juntamos a ZFC é muito forte: prova inclusive a Consistência (ZFC). E faz desaparecer - se houver - a prova de P<NP em ZFC. Gdes abcs 2017-08-20 10:21 GMT-03:00 Marcelo Finger <[email protected]>: > 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-Lwx6f6prmFp8OSPOBGD4yffe3xdY8n > h9ASTXs6Q0A%40mail.gmail.com. > -- fad ahhata alati, awienta Wilushati -- 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/CA%2BuR7BJf7cCDrQQP35BdNCKyukaWD-1uH-oBAuk3VpQW6DCLbw%40mail.gmail.com.
