Tem o texto? O Chaitin diz o mesmo para a CT- mas tem o efeito Scarpellini...
Sent from my iPhone On 30/08/2011, at 14:02, l...@inf.puc-rio.br wrote: > Caros colegas, > > Aqui o resumo da palestra do Maël Pegny: > > *PHYSICAL CT THESIS AND AARONSON’S NO-SUPERSEARCH PRINCIPLE : A COMPARISON* > > * > * > > ** > > *In the recent literature, it has been proposed to construe fundamental > statements of complexity and computability theory as physical principles. In > his seminal paper Quantum theory, the Church-Turing principle and the > universal quantum computer (1985,) David Deutsch defended the view that the > Church-Turing thesis should be understood as a physical principle : every > finitely realizable physical system can be perfectly simulated by a > universal model computing machine operating by finite means. More recently, > Scott Aaronson proposed to consider the P?=NP conjecture as another physical > principle, the No-supersearch principle : there is no physical means to > solve NP-complete problems in polynomial time. I will try to explain why it > is interesting to study these two proposals together, and what consequences > could be drawn from them for both physics and complexity theory.* > _______________________________________________ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
