Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with closed timelike curves:
TR11-108 | 8th August 2011
Scott Aaronson

Why Philosophers Should Care About Computational Complexity

Revisions: 2

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the ... more >>>

TR16-146 | 18th September 2016
Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini

Computability Theory of Closed Timelike Curves

We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid ... more >>>

ISSN 1433-8092 | Imprint