Scott Aaronson
  • Member for 11 years, 4 months
  • Last seen more than 4 years ago
A simple decision problem whose decidability is not known
Accepted answer
103 votes

The Matrix Mortality Problem for 2x2 matrices. I.e., given a finite list of 2x2 integer matrices M1,...,Mk, can the Mi's be multiplied in any order (with arbitrarily many repetitions) to produce the ...

View answer
Applicability of Church-Turing thesis to interactive models of computation
76 votes

Here's my favorite analogy. Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of ...

View answer
Techniques for showing that problem is in hardness "limbo"
49 votes

Showing that your problem is in coAM (or SZK) is indeed one of the main ways to adduce evidence for "hardness limbo." But besides that, there are several others: Show that your problem is in NP ∩...

View answer
Extended Church-Turing Thesis
Accepted answer
45 votes

Preparatory Rant I've gotta tell you, I don't see how talking about "proofs" of the CT or ECT adds any light to this discussion. Such "proofs" tend to be exactly as good as the assumptions they rest ...

View answer
Are there canonical non-relativizing techniques?
Accepted answer
41 votes

There's really only one "flagship" non-relativizing technique: namely, arithmetization (the technique used in the proofs of IP=PSPACE, MIP=NEXP, PP⊄SIZE(nk), MAEXP⊄P/poly, and several other ...

View answer
Should experts in TCS charge money to read proofs that P != NP?
40 votes

I have some "real-world experience" in this nascent industry (and no, I'm not talking about my $200,000 offer to Deolalikar :-) ) In January, a software developer emailed me that he had an attempted ...

View answer
Is $PH \subseteq PP$?
Accepted answer
38 votes

Huck, as Lance and Robin pointed out, we do have oracles relative to which PH is not in PP. But that doesn't answer your question, which was what the situation is in the "real" (unrelativized) world! ...

View answer
Rigour leading to insight
Accepted answer
35 votes

András, as you probably know, there are so many examples of what you're talking about that it's almost impossible to know where to start! However, I think this question can actually be a good one, if ...

View answer
$BQP$ vs $QMA$?
Accepted answer
34 votes

1) No implication is known in either direction. We know that P=NP implies P=PH. But we don't know if BQP and QMA are in PH, so maybe P could equal NP yet BQP and QMA still wouldn't collapse. (On ...

View answer
The unreasonable power of non-uniformity
33 votes

A flip answer is that this isn't the first thing about complexity theory that I'd try to explain to a layperson! To even appreciate the idea of nonuniformity, and how it differs from nondeterminism, ...

View answer
A decision problem which is not known to be in PH but will be in P if P=NP
31 votes

If an artificial example is really as good as a natural one, then I can indeed provide such an example! Edit: Furthermore, my example is "somewhat" less of a cheat than the one suggested by Ravi ...

View answer
Quantum computing project ideas
29 votes

I posted some quantum complexity theory project ideas at http://scottaaronson.com/blog/?p=471 (But beware, most of these are problems that have been open for years! My suggestion for an ...

View answer
Computational complexity of pi
Accepted answer
28 votes

OK, James Lee has pointed me to this 2011 paper by Samir Datta and Rameshwar Pratap, which proves that my language $L$ (encoding the digits of $\pi$) is in the fourth level of the counting hierarchy ($...

View answer
The cozy neighborhoods of "P" and of "NP-hard"
28 votes

The very terms "on the P-side" and "on the NP-side," and of course the question title, encourage us to imagine a "cozy neighborhood" surrounding P and another "cozy neighborhood" surrounding the NP-...

View answer
Why are so few natural candidates for NP-intermediate status?
27 votes

As others have pointed out, it's debatable to what extent the thing you're trying to explain is even true. One could argue that, in the 60s and 70s, theoretical computer scientists were just more ...

View answer
Is the Chomsky-hierarchy outdated?
25 votes

If anything in TCS is outdated, it's this inclusion hierarchy of the tiny subset of complexity classes that happened to be known / considered interesting in 1956. Rest in peace, Chomsky Hierarchy, ...

View answer
Interactive proofs for levels of the polynomial hierarchy
24 votes

This is a known (wonderful) open problem that I've worked on from time to time without success. Avi Wigderson and I mentioned the problem in our algebrization paper, where we raised the question of ...

View answer
How does the BosonSampling paper avoid easy classes of complex matrices?
Accepted answer
23 votes

Thanks for your question! There are two answers, depending on whether you're interested in the hardness results for exact or approximate BosonSampling. In the exact case, we prove that given any n-...

View answer
New algorithm for Discrete log and its implications for Quantum computing
Accepted answer
19 votes

Well, one crucial observation is that the new algorithm apparently only works for groups of the form $Z_{p^k}$ where $p$ is small --- it doesn't give a speedup for groups of the form $Z_p$. The ...

View answer
Is adiabatic quantum computing as powerful as the circuit model?
19 votes

Two quick clarifications: Adiabatic QC is typically "based on qubits" just as much as circuit-based QC is -- I don't know where you got the idea that it isn't! (Though one could also use qutrits or ...

View answer
Can relativization results be used to prove sentences formally independent?
Accepted answer
18 votes

There are no "natural" complexity-theory questions that have been proved independent of really powerful formal systems, such as ZF set theory or Peano Arithmetic. (One could certainly construct such ...

View answer
Approximate counting problem capturing BQP
Accepted answer
18 votes

Emanuele: Unfortunately, we don't know of any black-box problem capturing BQP as simple as the one you mentioned capturing BPP. Intuitively, this is because it's hard to talk about BQP without ...

View answer
Ed. Witten's new paper and the simulation of a quantum field theory
Accepted answer
17 votes

To complement what Joe wrote, and maybe explain this question a bit more (without answering it!): The computational complexity of simulating "realistic" quantum field theories has been considered an ...

View answer
Alan Turing's Contributions to Computer Science
Accepted answer
17 votes

This question is a lot like asking for Newton's contributions to physics, or Darwin's to biology! However, there's an interesting aspect to the question that many commenters have already seized on: ...

View answer
Do natural generalizations of P versus NP exist?
Accepted answer
15 votes

John, while your kind comments are appreciated, I confess that I don't understand how your question relates to the simple point I was making in the quoted remark. All I was saying was that we do know ...

View answer
How did TCS become conference-oriented rather than journal-oriented?
15 votes

While I don't know the answer to this question, it seems crucial that the phenomenon isn't limited at all to theoretical computer science. I believe SIGGRAPH plays the same sort of role for graphics, ...

View answer
Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$
Accepted answer
14 votes

I don't know a reference, but I think both of these should be doable. For your first oracle: for starters you'll want an oracle (call it $A_1$) that encodes exponentially-large $MAJORITY$ instances, ...

View answer
Consequences of $BQP \subseteq P/poly$?
Accepted answer
14 votes

I'd say we have no good reason to think BQP is in P/poly. We do have reasons to think that BQP is not in P/poly, but they're more-or-less identical to our reasons to think that BQP≠BPP. E.g., if ...

View answer
Can we decide whether a permanent has a unique term?
14 votes

Nice problem! It's not hard to give a reduction showing that, if one could solve your problem, then one could also solve the following problem, call it ISOLATED SUBSET SUM: Given integers a1,...,an, ...

View answer
Oracular separations between poly- and log-depth quantum circuits
Accepted answer
12 votes

I apologize; I was too glib when I wrote that. While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after ...

View answer