el problema

[Joao Marcos]

El problema que los informáticos no han podido resolver en 45 años
- La pregunta "¿P=NP?" trae de cabeza a los programadores desde 1971
por Ricardo Peña Marí (Universidad Complutense de Madrid)
http://tecnologia.elpais.com/tecnologia/2017/05/19/actualidad/1495202801_698394.html

[Thiago Nascimento da Silva]

O texto diz que se P = NP, então teríamos encontrado algoritmos, no caso existe, encontrar é outro trabalho.

--
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_Lgogt27%3DZtjcyDT-mrvxtC5BLD-JBW1rOxTuD%2BKdGXudw%40mail.gmail.com.

[Claus Akira Horodynski Matsushigue]

Pois é! Esta é uma pergunta (?) interessante!!! 

Se a solução do problema for (fosse) um EXISTE CLÁSSICO um algoritmo/programa  (i.e., existe exclusivamente da Lógica Clássica), certamente seria interessante, mas não serviria em nada prá esta questão prática que é da Computação. 

Prá Computação, falar que EXISTE um algoritmo, significa claramente, EXIBA - O!!!!! 

Abraços, Claus 

Em 22 de mai de 2017 7:06 PM, "Thiago Nascimento da Silva" <thiagna...@gmail.com> escreveu:

O texto diz que se P = NP, então teríamos encontrado algoritmos, no caso existe, encontrar é outro trabalho.

Em 22 de maio de 2017 18:18, Joao Marcos <boto...@gmail.com> escreveu:

El problema que los informáticos no han podido resolver en 45 años
- La pregunta "¿P=NP?" trae de cabeza a los programadores desde 1971
por Ricardo Peña Marí (Universidad Complutense de Madrid)
http://tecnologia.elpais.com/tecnologia/2017/05/19/actualidad/1495202801_698394.html

--
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 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_Lgogt27%3DZtjcyDT-mrvxtC5BLD-JBW1rOxTuD%2BKdGXudw%40mail.gmail.com.

--
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+unsubscribe@dimap.ufrn.br.

Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
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/CAOHRVBXONyhA%3Da3NGVSwWSStM8mfk4f6FWXQ_RGHKLq4BvCZQw%40mail.gmail.com.

[Famadoria]

Tem casos em que a gente pode provar que há um algoritmo sem exibi-lo. 

Sent from my iPhone

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 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/CAJh6kGUUAaPSzs3%2BfW9jEX_mUydum2kyzoVhGkw2cFbQxVL6Ow%40mail.gmail.com.

[Marcelo Finger]

2017-05-22 22:00 GMT-03:00 Famadoria <fama...@gmail.com>:
> Tem casos em que a gente pode provar que há um algoritmo sem exibi-lo.

Certamente. Basta mostrar que um problema é NP-completo que segue que
há uma redução polinomial para qualquer outro problema NP-completo.
Encontrar estas reduções são outros 500.

[]s


--
Marcelo Finger
Departament of Computer Science, IME
University of Sao Paulo
http://www.ime.usp.br/~mfinger

[Famadoria]

Preciso.

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 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/CABqmzx0q144ZVo-ZPZLLQXuXmAjmJ9yyeAcgZ4rahxxeeAE%3DfQ%40mail.gmail.com.

[Famadoria]

E tem coisa mais estranha aí.

Sent from my iPhone

> On 22 May 2017, at 22:39, Marcelo Finger <mfi...@ime.usp.br> wrote:
>

> --
> 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 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/CABqmzx0q144ZVo-ZPZLLQXuXmAjmJ9yyeAcgZ4rahxxeeAE%3DfQ%40mail.gmail.com.

[Samuel Gomes]

Prezados,

Aproveito para apresentar uma pergunta que anda pela minha cabeça nos últimos dias.

--> Existiria algum interesse para a Computação se algum desses problemas sobre Complexidade fosse, digamos assim, internalizado em ZF e mostrado ser uma equivalência ou uma consequência de algum principio de escolha (aqui principio de escolha significa alguma asserção que é encarada na literatura sempre no contexto de sua relação com o Axioma da Escolha, por exemplo ultrafiltros livres ou escolhas dependentes) ?

Minha pergunta não é meramente retórica, um professor de computação vai passar um ano em pos doc aqui na Ufba colaborando com os grupos de Matemática Aplicada e com a gente de Lógica, e eu sei que ele quer usar coisas relacionadas com o Axioma da Escolha em Computação.

A princípio eu disse pra ele, há alguns meses, que os argumentos em Computação devem ser todos construtivos, assim não faria sentido aplicar o Axioma da Escolha em Computação.

Porém vi em alguns posts de tcs stack exchange que certas afirmações sobre árvores que dependem de argumentos de escolha poderiam, em determinados pontos de vista, serem aceitos pela Teoria da Computação.

Bem, peço a opinião dos colegas.

Abraços,

[]s Samuel

[Samuel Gomes]

https://cstheory.stackexchange.com/questions/1923/which-interesting-theorems-in-tcs-rely-on-the-axiom-of-choice-or-alternatively

(esse é o post ao qual me referi)

[Joao Marcos]

Esta parte também não convence:

"En cambio, si fuera P=NP, habríamos encontrado algoritmos
polinomiales para todos esos problemas. La parte buena de ello es que
podríamos resolver, en tiempos muy cortos, problemas del viajante con
miles de ciudades y otros cientos de problemas útiles para los que hoy
tenemos algoritmos muy costosos, y eso sería beneficioso para la
industria, las comunicaciones y el desarrollo en general."

Da existência (exibida) de um algoritmo polinomial não se segue que
ele funcionará "en tiempo muy corto". Um algoritmo pode ser
"impraticável" (e praticamente inútil, na prática) sem cair na classe
dos problemas *intratáveis*.

JM


2017-05-23 2:15 GMT+02:00 Claus Akira Horodynski Matsushigue
<clau...@mat.unb.br>:

> 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
> 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/CAOHRVBXONyhA%3Da3NGVSwWSStM8mfk4f6FWXQ_RGHKLq4BvCZQw%40mail.gmail.com.
>
>

> --
> 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
> 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/CAJh6kGUUAaPSzs3%2BfW9jEX_mUydum2kyzoVhGkw2cFbQxVL6Ow%40mail.gmail.com.



--
http://sequiturquodlibet.googlepages.com/

[Hermógenes Oliveira]

Marcelo Finger <mfi...@ime.usp.br> escreveu:

> 2017-05-22 22:00 GMT-03:00 Famadoria <fama...@gmail.com>:
>> Tem casos em que a gente pode provar que há um algoritmo sem exibi-lo.
>
> Certamente. Basta mostrar que um problema é NP-completo que segue que
> há uma redução polinomial para qualquer outro problema NP-completo.
> Encontrar estas reduções são outros 500.

Olá, Marcelo.

Esta é uma pergunta sincera (não retórica):

Como poderíamos mostrar que um problema é NP-completo sem exibir uma
redução? Pergunto isso apenas porque todas as demonstrações desse tipo
que eu conheço exibem a redução. Você poderia citar algum contraexemplo
(referência bibliográfica)?

Quando penso a respeito, tenho dificuldade de vislumbrar como uma
demonstração dessas funcionaria. Para demonstrar que um problema é
NP-completo, além de demonstrar que o problema pertence à classe NP,
seria necessário demonstrar que o problema é NP-Hard ("NP-difícil" ?).
Até onde consigo ver, a única forma de fazer isso seria mostrar uma
redução polinomial do problema a outro problema comprovadamente
NP-completo ou relacionar diretamente o espaço das soluções do problema
com o modelo de computação subjacente (normalmente, máquinas de Turing)
como fez Cook com o SAT no artigo de 71. Existiria uma outra maneira?
O que significaria, neste contexto, demonstratar que existe uma redução
(construção, algorítimo) polinomial do problema sem exibir tal redução
(construção, algorítimo)? Se você conhece algum exemplo, eu estaria
muito interessado.

Consigo ver que, para resultados negativos, não seria necessário exibir
um algorítimo, pois poderíamos supor que há uma redução e extrair daí
uma contradição, mas esse tipo de raciocínio é construtivamente aceito.

Obviamente, se o problema é indecidível, ter uma redução (por exemplo,
para o problema da parada) não significa ter um algorítimo *para
solucionar do problema*. Mas, para o caso de problemas NP-completos,
não consigo ver como seria possível demonstrar NP-completude sem
fornecer as reduções e obter daí um algorítimo, possivelmente com ajuda
de resultados e reduções já conhecidas.

--
Hermógenes Oliveira

[Francisco Antonio Doria]

Há uns vinte anos soube que Solovay discutiu várias versões do número Omega de Chaitin, com propriedades estranhíssimas. Discuti a coisa com o Newton e saímos à cata de outros exemplos agualmente peculiares. Newton sugeriu uma versão do Omega cuja construção invocava explicitamente o Axioma da Escolha. Isto foi publicado pela gente nalgum canto, não lembro exato onde. 

--
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 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/87a864gfn1.fsf%40camelot.oliveira.

--

fad

ahhata alati, awienta Wilushati

[Marcelo Finger]

Oi Hermógenes.

> Como poderíamos mostrar que um problema é NP-completo sem exibir uma
> redução?

Para mostrar que um problema de DECISÂO é NP-completo (a classe NP só
é definida para problemas que decidem se um elemento possui uma dada
propriedade), precisamos mostrar duas coisas:

a) Que ele está na classe NP. Para isso, precisamos mostrar que,
quando o elemento dado possui a propriedade, existe um passo não
determinístico (um chute) que gera uma _estrutura auxiliar_ e com essa
estrutura auxiliar e o elemento dado, podemos verificar e um número
polinomial de passos que o elemento possui a propriedade.

Por exemplo, se o elemento é uma fórmula na lógica proposicional
clássica, a propriedade é ser satisfazível, então a estrutura auxiliar
é uma valoração das variáveis atốmicas, com a qual mostramos em tempo
linear no número de átomos da fórmula que esta é satisfazível.

Há uma fundamental assimetria aqui, pois no caso de a fórmula ser
insatisfazível não precisamos mostrar nada.

b) Que ele é NP-difícil. Para isso, basta reduzir polinomialmente a
decisão de UM problema NP-completo na decisão dada.

Aqui a gente precisa apresentar UMA redução, e ganha "de grátis" a
existência de reduções para todos os outros problemas NP-completos.
Na realidade, não é "de grátis", mas pela transitividade de reduções
polinomiais, que também é polinomial.

Cook demonstrou que fórmulas da LPC simulam qqer problema de decisão
em máquinas de turing não-determinística de tempo polinomial, de forma
que dado um problema em uma máquina de Turing MT em NP, computa-se uma
fórmula A tal que a MT pára com resposta SIM sse a fórmula A é SAT.
Ou seja, todo problema em NP se reduz a SAT.

[Marcelo Finger]

Oi Samuel.

> A princípio eu disse pra ele, há alguns meses, que os argumentos em Computação devem ser
> todos construtivos, assim não faria sentido aplicar o Axioma da Escolha em Computação.

Não concordo. Se v consegue apresentar uma propriedade desconhecida
de um problema interessante, pouco importa se a prova é construtiva ou
não. Na hora de buscar um algoritmo (construtivo) é bom saber que a
propriedade que se quer demonstrar é verdadeira.

Tem muita prova importante de complexidade de problemas em que os
algoritmos são totalmente não-determinísticos, e a geração de um
algoritmo não trivial (ou seja, que não gera-e-testa todos os casos)
involve a exploração de OUTRAS propriedades. Mesmo assim, a prova
original é considerada totalmente válida.

Eu mesmo me deparei com um caso assim recentemente. Havia uma prova
de que um problema de decisão envolvendo Quantificadores de Contagem
era NP-completo, mas o algoritmo que o Ian Pratt-Hartman apresentou
era totalmente não-determinístico, e eu usei uma modificação do
algoritmo branch-and-bound de programação linear inteira para gerar um
algoritmo determinístico.

[]s

2017-05-23 9:42 GMT-03:00 Francisco Antonio Doria <fama...@gmail.com>:
> Há uns vinte anos soube que Solovay discutiu várias versões do número Omega
> de Chaitin, com propriedades estranhíssimas. Discuti a coisa com o Newton e
> saímos à cata de outros exemplos agualmente peculiares. Newton sugeriu uma
> versão do Omega cuja construção invocava explicitamente o Axioma da Escolha.
> Isto foi publicado pela gente nalgum canto, não lembro exato onde.
>
> 2017-05-23 5:07 GMT-03:00 Hermógenes Oliveira

> <hermogene...@student.uni-tuebingen.de>:

> --
> 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
> 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%2BuR7BKLad8ocCVePEPWNHd8aNAYX%3DHG0FOY50F%3DtEu-6G7Zjg%40mail.gmail.com.

[Famadoria]

Um dos exemplos: um real do qual não podemos calcular um só dígito.

Sent from my iPhone

> Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CABqmzx3KW_fPkKr2LOpcZnN%2BfZbCrf52WfWkRZPTOb4WQnanRw%40mail.gmail.com.

[Rodrigo Freire]

Prezado Samuel,

Você teria que procurar um enunciado que não seja absoluto para o universo construtível L. De fato, temos o seguinte resultado, já aludido em uma das respostas nesse link que você enviou:

- Se S é um enunciado absoluto para L em ZF, e S é demonstrável em ZFC, então S é demonstrável em ZF.

Dem.: Se S é teorema de ZFC, então ZF demonstra que S vale no universo construtível L, pois ZF demonstra que L satisfaz todos os axiomas de ZFC. Mas S é absoluto para L, ou seja, ZF demonstra que "L satisfaz S é equivalente a S". Portanto, ZF demonstra S. Fim.

Não há nada especial com o axioma da escolha no resultado acima, apenas usamos que ZF demonstra que este axioma vale em L. O mesmo se aplica, por exemplo, para GCH, que é mais forte que AC: Se S é demonstrável em ZF + GCH, então S é demonstrável em ZF. Você poderia usar até mesmo V=L para demonstrar S, pois ZF + V=L é conservativa sobre ZF para enunciados absolutos para L em ZF. 

Se assumirmos (bastante razoável) que qualquer enunciado da teoria da computação pode ser codificado na aritmética de segunda ordem, então você teria que procurar exemplos que sejam pelo menos Delta^1_3 na hierarquia analítica, pois os enunciados Sigma^1_2 ou Pi^1_2 em ZF são absolutos para L em ZF. Não parece fácil encontrar exemplo de interesse da teoria da computação que não seja Sigma^1_2 ou Pi^1_2 em ZF.

Abraço

Rodrigo

[Samuel Gomes]

... Obrigado, Doria, Finger e Rodrigo,

Após parar para pensar no tal resultado de Absoluteness que o Rodrigo comentou (grato novamente !),
vejo que, na verdade, para mim a situação é até melhor do que eu pensava.

A mensagem de Rodrigo diz:

"Você teria que procurar um enunciado que não seja absoluto para o universo construtível L."

Bem, essa afirmação pressupõe que a minha preocupação inicial era, da mesma maneira que a pessoa
que postou a pergunta no TCS Stack Exchange, "procurar afirmações da Ciência da Computação que necessitem
do Axioma da Escolha". Mas não era essa a minha preocupação !

O que eu estou preocupado, estimulado por esse visitante de computação que veio fazer pós-doc aqui, é exatamente
COMO USAR o Axioma da Escolha em Computação.

E, se bem entendi a explicação do Rodrigo (e mais algumas que encontrei depois), na verdade estou no melhor dos mundos
porque posso usar o Axioma da Escolha "como muleta", no sentido de que

"Se eu consigo uma demonstração com Axioma da Escolha, eu posso ficar tranquilo porque na verdade ele não era necessário
e existe uma demonstração construtiva em ZF" (exibi-la sim que pode ser um problema, mas ter essa informação me parece sensacional, não ?)

Por exemplo, para os tais enunciados S da aritmética que são Sigma^1_2 ou Pi^1_2, então vale o absoluteness para L e teremos o:

"Se ZFC prova S, então ZF prova S"

Então o Axioma da Escolha só serviu como uma "muleta não-construtiva" para eu chegar na informação de que existe uma prova construtiva para S
(supondo o problema internalizado em Teoria dos Conjuntos, etc.)

Concordam ?

Atés,

[]s  Samuel

[Rodrigo Freire]

Sim, para mostrar que um enunciado absoluto para L em ZF vale em ZF você pode usar o axioma da escolha *global*, além de GCH, diamante, etc. E parece muito difícil encontrar um enunciado "natural" em teoria da computação que não seja absoluto para L. 

Abraço

Rodrigo




Enviado do meu iPhone

--

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 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/8a4c150d-4441-4418-8ed1-65585da6b362%40dimap.ufrn.br.