Computing NP-complete problems in polynomial time by means of Physics

Abstract

Can NP-complete problems be solved efficiently in the physical universe? Some researchers have claimed to be able to solve NP-complete problems in polynomial time by encoding the problem in the state of a physical system and letting it evolve naturally, according to the laws of physics. However, their proposals have not proven to be very effective in practice. Additionally, there are several reasons to believe that those methods would not work if P 6= NP. We present some physical assumptions (both from classical physics and quantum mechanics) that would allow us to provably solve NP-complete problems in polynomial time by means of Physics, even if P 6= NP and NP 6⊂ BQP. We also study if our proposals are consistent with currently known laws of Physics.

¿Podemos resolver problemas NP-completos en tiempo polinómico dejando que ciertos entornos físicos evolucionen de manera natural conforme a las leyes de la física? Varios estudios así lo parecen afirmar, sin embargo, los métodos propuestos no han resultado ser muy efectivos en la práctica, y de hecho hay razones para pensar que no sería posible si P 6= NP. Planteamos algunas suposiciones físicas (basadas tanto en la física clásica como en la mecánica cuántica) que nos permitirían resolver problemas NP-completos en tiempo polinómico en un Universo con dichas características, aunque P 6= NP y NP 6⊂ BQP, y tratamos de estudiar si dichas suposiciones son consistentes con principios conocidos de la Física.