Obrigado, João Marcos, por este post. Pena que Scott Aronson não fale sobre o folclore que circula a respeito, e não publicado. Um dos raros papers que o mencionam é um preprint de S. ben-David e S. Halevy, primeira versão de 1994, mas com uma versão de 2002, creio. Nunca foi publicado, sei lá o motivo.
Dois exemplos deste folclore: - A função contraexemplo para P=NP cresce, nos seus picos, ao menos tão rápido quanto a Busy Beaver. - Se P<NP e P=NP forem independentes de ZFC, então P<NP é verdadeiro no modelo standard da aritmética (isso se ZFC tiver um modelo sound). - Se P=NP for verdadeiro nesse modelo sound, então será demonstrável numa aritmética com a mesma ``força de prova'' que PA (suposta consistente, etc). Quem nos passou tais dicas foi o Kreisel. 2017-01-06 19:28 GMT-02:00 Joao Marcos <jmar...@dimap.ufrn.br>: > Um update sobre o resultado anunciado há pouco mais de um ano por Babai: > https://rjlipton.wordpress.com/2017/01/04/babais-result- > still-a-breakthrough/ > Já não se fala mais em tempo quase-polinomial, mas "apenas" em tempo > subexponencial. > > * * * > > Aproveito para enviar um link ao detalhado survey sobre P=?NP recém > divulgado por Scott Aaronson: > http://www.scottaaronson.com/papers/pnp.pdf > > * * * > > JM > > 2015-11-28 11:36 GMT-02:00 Joao Marcos <jmar...@dimap.ufrn.br>: > > Ainda sobre o isomorfismo de grafos: > > > > A Little More on the Graph Isomorphism Algorithm > > https://rjlipton.wordpress.com/2015/11/21/a-little-more- > on-the-graph-isomorphism-algorithm/ > > > > A agora já afamada palestra de Babai (parte I) pode ser conferida aqui: > > http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4 > > Muito mais pode(rá) ser encontrado aqui: > > http://people.cs.uchicago.edu/~laci/quasipoly.html > > > > > > JM > > > > 2015-11-18 8:57 GMT-03:00 Joao Marcos <jmar...@dimap.ufrn.br>: > >> Se estiver correto, o resultado de Babai é um avanço extremamente > importante: > >> > >> "The graph isomorphism problem is the computational problem of > >> determining whether two finitegraphs are isomorphic. > >> Besides its practical importance, the graph isomorphism problem is a > >> curiosity in computational complexity theory as it is one of a very > >> small number of problems belonging to NP neither known to be solvable > >> in polynomial time nor NP-complete: it is one of only 12 such problems > >> listed byGarey & Johnson (1979), and the only one of that list whose > >> complexity remains unresolved." > >> https://en.wikipedia.org/wiki/Graph_isomorphism_problem > >> > >> Aqui uma referência acessível sobre o assunto: > >> https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem > >> > >> JM > >> > >> 2015-11-18 7:26 GMT-03:00 Famadoria <famado...@gmail.com>: > >>> Esse resultado se conhece desde 78. É "se PRA não prova P < NP então > há um > >>> algoritmo exponencial para tais problemas que cresce como exp da > função de > >>> Ramsey." > >>> > >>> A prova é razoavelmente fácil. > >>> > >>> Sent from my iPhone > >>> > >>> Begin forwarded message: > >>> > >>> From: > >>> Date: 13 de novembro de 2015 22:47:10 GMT+1 > >>> To: famado...@gmail.com > >>> Subject: Graph Isomorphism > >>> > >>> Hey Francisco, > >>> > >>> Je me demande ce que tu deviens? > >>> > >>> J'ai eu une pensee pour toi en croisant cette nouvelle: > >>> > >>> http://news.sciencemag.org/math/2015/11/mathematician- > claims-breakthrough-complexity-theory > >>> > >>> Babai est un tueur... > >>> > >>> Bien a toi > >>> > >>> Eric ;=0)))) > >>> > >>> -- > >>> > >>> « Les chanceux sont ceux qui arrivent à tout ; les malchanceux, ceux à > qui > >>> tout arrive. » - Labiche > >>> > >>> -- > >>> 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 logica-l+unsubscr...@dimap.ufrn.br. > >>> Para postar nesse grupo, envie um e-mail para logica-l@dimap.ufrn.br. > >>> Acesse esse grupo em > >>> http://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/9519642A-E1BE-428A-A514-F8D3CF8BD5CE%40gmail.com. > >> > >> > >> > >> -- > >> http://sequiturquodlibet.googlepages.com/ > > > > > > > > -- > > http://sequiturquodlibet.googlepages.com/ > > > > -- > http://sequiturquodlibet.googlepages.com/ > > -- > 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 logica-l+unsubscr...@dimap.ufrn.br. > Para postar neste grupo, envie um e-mail para logica-l@dimap.ufrn.br. > 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_Lg%2Bx-DzvRgeEr%3D8yt_ > fYsgzv1uC%2BzXoVsbCHfMqWhgkVg%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 logica-l+unsubscr...@dimap.ufrn.br. Para postar neste grupo, envie um e-mail para logica-l@dimap.ufrn.br. 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%2BuR7BJTiuT%3DTeFcNABK-DqyJbw9E0xXYVKArphcjeesj-P0LQ%40mail.gmail.com.
