1205.6658 (Michel Feldmann)

From classical versus quantum algorithms to P versus NP    [PDF]

Michel Feldmann

What is the powerful ingredient which allows a dramatic speed-up of quantum computation over classical algorithms? We propose that this ingredient is an implicit use of the Bayesian probability theory. Furthermore, we argue that both classical and quantum computation are special cases of probability reasoning. On these grounds, introducing Bayesian probability theory in classical computation as well, we reduce a typical NP problem, namely 3-SAT, to a linear programming problem. According to algorithmic complexity theory, this proves that P=NP.

View original: http://arxiv.org/abs/1205.6658