Um dos exemplos: um real do qual não podemos calcular um só dígito. Sent from my iPhone
> On 23 May 2017, at 09:58, Marcelo Finger <[email protected]> wrote: > > 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 <[email protected]>: >> 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 >> <[email protected]>: >>> >>> Marcelo Finger <[email protected]> escreveu: >>> >>>> 2017-05-22 22:00 GMT-03:00 Famadoria <[email protected]>: >>>>> 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 [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/87a864gfn1.fsf%40camelot.oliveira. >> >> >> >> >> -- >> fad >> >> ahhata alati, awienta Wilushati >> >> -- >> 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 >> 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. > > > > -- > Marcelo Finger > Departament of Computer Science, IME > University of Sao Paulo > http://www.ime.usp.br/~mfinger > > -- > 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/CABqmzx3KW_fPkKr2LOpcZnN%2BfZbCrf52WfWkRZPTOb4WQnanRw%40mail.gmail.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/EB371E45-0EB5-4FC9-85DB-6733FCA036EA%40gmail.com.
