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 <[email protected]>: > 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 <[email protected]>: >> 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 <[email protected]>: >>> 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: [email protected] >>> 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 [email protected]. >>> Para postar nesse grupo, envie um e-mail para [email protected]. >>> 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 [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_Lg%2Bx-DzvRgeEr%3D8yt_fYsgzv1uC%2BzXoVsbCHfMqWhgkVg%40mail.gmail.com.
