Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXTENDED CHURCH-TURING THESIS:
Reports tagged with Extended Church-Turing Thesis:
TR02-062 | 19th November 2002
Andrew Chi-Chih Yao

Classical Physics and the Church-Turing Thesis

Would physical laws permit the construction of computing machines
that are capable of solving some problems much faster than the
standard computational model? Recent evidence suggests that this
might be the case in the quantum world. But the question is of
great interest even in the realm of classical physics. ... more >>>


TR10-128 | 15th August 2010
Scott Aaronson

The Equivalence of Sampling and Searching

Revisions: 1

In a sampling problem, we are given an input $x\in\left\{0,1\right\} ^{n}$, and asked to sample approximately from a probability
distribution $D_{x}$ over poly(n)-bit strings. In a search problem, we are given an input
$x\in\left\{ 0,1\right\} ^{n}$, and asked to find a member of a nonempty set
$A_{x}$ with high probability. ... more >>>


TR14-044 | 2nd April 2014
Daniel Dewey

Additively efficient universal computers

We give evidence for a stronger version of the extended Church-Turing thesis: among the set of physically possible computers, there are computers that can simulate any other realizable computer with only additive constant overhead in space, time, and other natural resources. Complexity-theoretic results that hold for these computers can therefore ... more >>>




ISSN 1433-8092 | Imprint