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 <hermogenes.oliveira@student.u ni-tuebingen.de>: > Marcelo Finger <mfin...@ime.usp.br> escreveu: > > > 2017-05-22 22:00 GMT-03:00 Famadoria <famado...@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 > > -- > 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/di > map.ufrn.br/group/logica-l/. > Para ver esta discussão na web, acesse https://groups.google.com/a/di > map.ufrn.br/d/msgid/logica-l/87a864gfn1.fsf%40camelot.oliveira. > -- 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%2BuR7BKLad8ocCVePEPWNHd8aNAYX%3DHG0FOY50F%3DtEu-6G7Zjg%40mail.gmail.com.