Fetching the paper…
Reading the bibliography…
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.
Computing machinery and intelligence
A. M. Turing · 1950
Earlier work this paper cites.
Fact, Fiction, and Forecast
N. Goodman · 1955
Earlier work this paper cites.
A behavioral model of rational choice
H. A. Simon · 1955
Earlier work this paper cites.
The unreasonable effectiveness of mathematics in the natural sciences
E. Wigner · 1960
Earlier work this paper cites.
Minds, machines, and Gödel
J. R. Lucas · 1961
Earlier work this paper cites.
Knowledge and Belief
J. Hintikka · 1962
Earlier work this paper cites.
The intrinsic computational difficulty of functions
A. Cobham · 1965
Earlier work this paper cites.
On the computational complexity of algorithms
J. Hartmanis and R. E. Stearns · 1965
Earlier work this paper cites.
Schnelle Multiplikation großer Zahlen
A. Schönhage and V. Strassen · 1971
Earlier work this paper cites.
On the uniform convergence of relative frequencies of events to their probabilities
V. Vapnik and A. Chervonenkis · 1971
Earlier work this paper cites.
Some estimates of the information transmitted by quantum communication channels
A. S. Holevo · 1973
Earlier work this paper cites.
Relativizations of the P=?NP question
T. Baker, J. Gill, and R. Solovay · 1975
Earlier work this paper cites.
On the structure of polynomial time reducibility
R. E. Ladner · 1975
Earlier work this paper cites.
Agreeing to disagree
R. J. Aumann · 1976
Earlier work this paper cites.
Minds, brains, and programs
J. Searle · 1980
Earlier work this paper cites.
Computing a perfect strategy for nxn chess requires time exponential in n
A. Fraenkel and D. Lichtenstein · 1981
Earlier work this paper cites.
Hex is PSPACE-complete
S. Reisch · 1981
Earlier work this paper cites.
Simulating physics with computers
R. P. Feynman · 1982
Earlier work this paper cites.
Judgment Under Uncertainty: Heuristics and Biases
D. Kahneman, P. Slovic, and A. Tversky · 1982
Earlier work this paper cites.
On the complexity of chess
J. A. Storer · 1983
Earlier work this paper cites.
Computational complexity and the universal acceptance of logic
C. Cherniak · 1984
Earlier work this paper cites.
How to construct random functions
O. Goldreich, S. Goldwasser, and S. Micali · 1984
Earlier work this paper cites.
Subrecursion: Functions and Hierarchies
H. E. Rose · 1984
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
Earlier work this paper cites.
Bounded complexity justifies cooperation in the finitely repeated prisoners’ dilemma
A. Neyman · 1985
Earlier work this paper cites.
Learning regular sets from queries and counterexamples
D. Angluin · 1987
Earlier work this paper cites.
Does co-NP have short interactive proofs?
R. B. Boppana, J. Håstad, and S. Zachos · 1987
Earlier work this paper cites.
Classifying the computational complexity of problems
L. J. Stockmeyer · 1987
Earlier work this paper cites.
Multi-prover interactive proofs: how to remove the intractability assumptions
M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson · 1988
Earlier work this paper cites.
Minimum disclosure proofs of knowledge
G. Brassard, D. Chaum, and C. Crépeau · 1988
Earlier work this paper cites.
Wormholes, time machines, and the weak energy condition
M. S. Morris, K. S. Thorne, and U. Yurtsever · 1988
Earlier work this paper cites.
Computational limitations on learning from examples
L. Pitt and L. Valiant · 1988
Earlier work this paper cites.
Every planar map is four-colorable
K. Appel and W. Haken · 1989
Earlier work this paper cites.
Learnability and the Vapnik-Chervonenkis dimension
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1989
Earlier work this paper cites.
The knowledge complexity of interactive proof systems
S. Goldwasser, S. Micali, and C. Rackoff · 1989
Earlier work this paper cites.
The Emperor’s New Mind
R. Penrose · 1989
Earlier work this paper cites.
Nondeterministic exponential time has two-prover interactive protocols
L. Babai, L. Fortnow, and C. Lund · 1991
Earlier work this paper cites.
Quantum mechanics near closed timelike lines
D. Deutsch · 1991
Earlier work this paper cites.
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
O. Goldreich, S. Micali, and A. Wigderson · 1991
Earlier work this paper cites.
A foundational delineation of poly-time
D. Leivant · 1991
Earlier work this paper cites.
Representation and Reality
H. Putnam · 1991
Earlier work this paper cites.
Relativizing versus nonrelativizing techniques: the role of local checkability
S. Arora, R. Impagliazzo, and U. Vazirani · 1992
Earlier work this paper cites.
A new recursion-theoretic characterization of the polytime functions
S. Bellantoni and S. A. Cook · 1992
Earlier work this paper cites.
The Rediscovery of the Mind
J. Searle · 1992
Earlier work this paper cites.
IP=PSPACE
A. Shamir · 1992
Earlier work this paper cites.
The history and status of the P versus NP question
M. Sipser · 1992
Cited alongside, same era.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1993
Cited alongside, same era.
Finite model theory - a personal perspective
R. Fagin · 1993
Cited alongside, same era.
The role of relativization in complexity theory
L. Fortnow · 1994
Cited alongside, same era.
Non-Turing computers and non-Turing computability
M. Hogarth · 1994
Cited alongside, same era.
Cryptographic limitations on learning Boolean formulae and finite automata
M. J. Kearns and L. G. Valiant · 1994
Cited alongside, same era.
An Introduction to Computational Learning Theory
One complexity theorist’s view of quantum computing
L. Fortnow · 2003
Later among the works it cites.
A short history of computational complexity
L. Fortnow and S. Homer · 2003
Later among the works it cites.
Polynomial time and extravagant models, in The tale of one-way functions
L. A. Levin · 2003
Later among the works it cites.
From cbits to qbits: teaching computer scientists quantum mechanics
N. D. Mermin · 2003
Later among the works it cites.
Neural and super-Turing computing
H. T. Siegelmann · 2003
Later among the works it cites.
Multilinear formulas and skepticism of quantum computing
S. Aaronson · 2004
Later among the works it cites.
What Is Thought?
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
M. J. Kearns and U. V. Vazirani · 1994
Cited alongside, same era.
Computational Complexity
C. H. Papadimitriou · 1994
Cited alongside, same era.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1994
Cited alongside, same era.
On the power of quantum computation
D. Simon · 1994
Cited alongside, same era.
Darwin’s Dangerous Idea: Evolution and the Meanings of Life
D. C. Dennett · 1995
Cited alongside, same era.
Reasoning about Knowledge
R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi · 1995
Cited alongside, same era.
E. B. Baum · 2004
Later among the works it cites.
Consequences and limits of nonlocal strategies
R. Cleve, P. Høyer, B. Toner, and J. Watrous · 2004
Later among the works it cites.
On quantum computing
O. Goldreich · 2004
Later among the works it cites.
Epistemic virtues, metavirtues, and computational complexity
A. Morton · 2004
Later among the works it cites.
The complexity of agreement
S. Aaronson · 2005
Later among the works it cites.
NP-complete problems and physical reality
S. Aaronson · 2005
Later among the works it cites.
Quantum computing, postselection, and probabilistic polynomial-time
S. Aaronson · 2005
Later among the works it cites.
Introduction to the Theory of Computation (Second Edition)
M. Sipser · 2005
Later among the works it cites.
Learning a circuit by injecting values
D. Angluin, J. Aspnes, J. Chen, and Y. Wu · 2006
Later among the works it cites.
Average-case complexity
A. Bogdanov and L. Trevisan · 2006
Later among the works it cites.
Settling the complexity of two-player Nash equilibrium
X. Chen and X. Deng · 2006
Later among the works it cites.
The complexity of computing a Nash equilibrium
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou · 2006
Later among the works it cites.
The God Delusion
R. Dawkins · 2006
Later among the works it cites.
Quantum versus classical proofs and advice
S. Aaronson and G. Kuperberg · 2007
Later among the works it cites.
The PCP theorem by gap amplification
I. Dinur · 2007
Later among the works it cites.
How to do philosophy
P. Graham · 2007
Later among the works it cites.
Quantum Computer Science: An Introduction
N. D. Mermin · 2007
Later among the works it cites.
The Turing test as interactive proof
S. M. Shieber · 2007
Later among the works it cites.
Evolvability
L. G. Valiant · 2007
Later among the works it cites.
P, NP and mathematics - a computational complexity perspective
A. Wigderson · 2007
Later among the works it cites.
Algebrization: a new barrier in complexity theory
S. Aaronson and A. Wigderson · 2008
Later among the works it cites.
On basing lower-bounds for learning on worst-case assumptions
B. Applebaum, B. Barak, and D. Xiao · 2008
Later among the works it cites.
Computational Complexity: A Conceptual Perspective
O. Goldreich · 2008
Later among the works it cites.
Entangled games are hard to approximate
J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and T. Vidick · 2008
Later among the works it cites.
An Introduction to Kolmogorov Complexity and Its Applications (3rd ed.)
M. Li and P. M. B. Vitányi · 2008
Later among the works it cites.
Quantum computational complexity
J. Watrous · 2008
Later among the works it cites.
Closed timelike curves make quantum and classical computing equivalent
S. Aaronson and J. Watrous · 2009
Later among the works it cites.
Complexity Theory: A Modern Approach
S. Arora and B. Barak · 2009
Later among the works it cites.
C. H. Bennett, D. Leung, G. Smith, and J. A. Smolin · 2009
Later among the works it cites.
Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities
X. Chen, D. Dai, Y. Du, and S.-H. Teng · 2009
Later among the works it cites.
Fully homomorphic encryption using ideal lattices
C. Gentry · 2009
Later among the works it cites.
Is it enough to get the behavior right?
H. J. Levesque · 2009
Later among the works it cites.
Knowledge, creativity and P versus NP, 2009
A. Wigderson · 2009
Later among the works it cites.
A Primer on Pseudorandom Generators
O. Goldreich · 2010
Later among the works it cites.
The Beginning of Infinity: Explanations that Transform the World
D. Deutsch · 2011
Closest in time.
Multiplying 10-digit numbers using Flickr: the power of recognition memory
A. Drucker · 2011
Closest in time.
The quantum mechanics of time travel through post-selected teleportation
S. Lloyd, L. Maccone, R. Garcia-Patron, V. Giovannetti, and Y. Shikano · 2011
Closest in time.
The Nature of Computation
C. Moore and S. Mertens · 2011
Closest in time.