Fwd: Graph Isomorphism

48 views
Skip to first unread message

Famadoria

unread,
Nov 18, 2015, 5:26:49 AM11/18/15
to 'Patrick Terrematte' via Logica-L
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: fama...@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:


Babai est un tueur...

Bien a toi

Eric ;=0))))

--

« Les chanceux sont ceux qui arrivent à tout ; les malchanceux, ceux à qui tout arrive. » - Labiche

Joao Marcos

unread,
Nov 18, 2015, 6:57:44 AM11/18/15
to Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
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
> --
> 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+u...@dimap.ufrn.br.
> Para postar nesse grupo, envie um e-mail para logi...@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/

Famadoria

unread,
Nov 18, 2015, 3:02:29 PM11/18/15
to logi...@dimap.ufrn.br
Foi Kreisel quem chamou a atenção do Newton e minha para essa característica de tais problemas - ou polinomiais ou (dada a condição que mencionei) exponenciais de lentíssimo crescimento. Parecem estar na fronteira mesmo.


Sent from my iPhone
> --
> 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+u...@dimap.ufrn.br.
> Para postar neste grupo, envie um e-mail para logi...@dimap.ufrn.br.
> Visite este grupo em http://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_Li0OX1ZdtPdVOUiiORXiXt16eTkmyryj3QBRDBLZbBdoQ%40mail.gmail.com.

Joao Marcos

unread,
Nov 28, 2015, 8:37:02 AM11/28/15
to Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
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
--
http://sequiturquodlibet.googlepages.com/

Joao Marcos

unread,
Jan 6, 2017, 4:29:03 PM1/6/17
to Lista acadêmica brasileira dos profissionais e estudantes da área de LOGICA
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
--
http://sequiturquodlibet.googlepages.com/

Francisco Antonio Doria

unread,
Jan 7, 2017, 5:18:08 AM1/7/17
to logi...@dimap.ufrn.br
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. 

--
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+unsubscribe@dimap.ufrn.br.
Para postar neste grupo, envie um e-mail para logi...@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
Reply all
Reply to author
Forward
0 new messages