2026-06-28T04:56:01Zhttps://docta.ucm.es/rest/oai/requestoai:docta.ucm.es:20.500.14352/53832023-09-06T22:11:01Zcom_20.500.14352_1col_20.500.14352_8
Docta Complutense
advisor
Rodríguez Laguna, Ismael
advisor
Rodríguez Laguna, Javier
author
Carrillo Redondo, Víctor
2023-06-16T14:57:07Z
2023-06-16T14:57:07Z
2021-09
https://hdl.handle.net/20.500.14352/5383
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.
eng
Atribución-NoComercial 3.0 España
Computing NP-complete problems in polynomial time by means of Physics
bachelor thesis
URL
https://docta.ucm.es/bitstreams/dde53980-f75d-465a-bdd1-78b527f192b1/download
File
MD5
b9f6db237500a5f04d7d1ae2f4c0854c
1873538
application/pdf
CARRILLO REDONDO 53668_VICTOR_CARRILLO_REDONDO_TFG_Victor_Carrillo_Redondo_1006096_158843533.pdf