Skip to main content
U.S. flag

An official website of the United States government

Dot gov

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Https

Secure .gov websites use HTTPS
A lock ( ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

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

Keywords

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