Black holes, quantum mechanics, and the limits of polynomial-time computability

Published: September 01, 2016

Author(s)

Stephen P. Jordan

Abstract

Which computational problems can be solved in polynomial time and which cannot? Though seemingly technical, this question has wide-ranging implications and brings us to the heart of both theoretical computer science and modern physics.
Citation: XRDS: crossroads (ACM's undergraduate magazine)
Volume: 23
Issue: 1
Pub Type: Others

Keywords

quantum computing, complexity theory
Created September 01, 2016, Updated November 10, 2018