In this paper we discuss physical aspects of intractable (NP-complete) computing problems. We show, using a specific model, that a quantum-mechanical computer can in principle solve an NP-complete problem in polynomial time; however, it would use an exponentially large energy for that computation. We conjecture that our model reflects a complementarity principle concerning the time and the energy needed to perform an NP-complete computation.

• Received 16 June 1992

DOI:https://doi.org/10.1103/PhysRevA.48.116