Obituaries of dead conjectures

Question

I am looking for conjectures about algorithms and complexity that were viewed credible by many at some point in time, but later they were either disproved, or at least disbelieved, due to mounting counter-evidence. Here are two examples:

1. Random oracle hypothesis: relationships between complexity classes that hold for almost all relativized worlds, also hold in the unrelativized case. This was disproved by the result $IP=PSPACE$, and by showing that $IP^X\neq PSPACE^X$ holds for almost all random oracles $X$, see The Random Oracle Hypothesis is False.

2. Bounded error randomness properly extends the power of polynomial time (i.e., $P\neq BPP$). This was believed for a while, but later, due to sophisticated derandomization results and their connections to circuit complexity, the opposite conjecture ($P=BPP$) has become prevalent (although still open).

Which are some other conjectures that failed the test of time?

Answer 1

$\mathsf{NL} \neq \mathsf{coNL}$. Prior to the result that these two were equal, I think it was widely believed that they were distinct, by analogy with the belief that $\mathsf{NP} \neq \mathsf{coNP}$ (i.e. the general principle that "nondeterministism and co-nondeterminism are different"; this turned out to be false under space complexity bounds that were at least logarithmic).

Answer 2

Prior to $\mathsf{IP} = \mathsf{PSPACE}$, it was thought possible that even $\mathsf{coNP}$ wasn't contained in $\mathsf{IP}$: in Fortnow-Sipser 1988 they conjectured this to be the case and gave an oracle relative to which it was true.

Answer 3

The $\mathsf{3SUM}$-conjecture: That any deterministic algorithm for $\mathsf{3SUM}$ requires $\Omega(n^2)$ time.

This was disproven in 2014, by Allan Grønlund and Seth Pettie, who gave a deterministic algorithm that runs in $O(n^2/(\log n/\log \log n)^{2/3})$ time [1].

[1] Threesomes, Degenerates, and Love Triangles. Allan Grønlund and Seth Pettie. In Foundations of Computer Science (FOCS) 2014, pp. 621-630. arXiv:1404.0799 [cs.DS]

Answer 4

Constant-width branching programs require more than polynomial length to count: After Furst-Saxe-Sipser and Ajtai in 1981 showed that AC⁰ circuits can't count, a natural next step seemed to be to show that constant-width branching programs of polynomial length couldn't count, which was widely conjectured to hold. David Barrington in 1986 showed that they not only can they count but that they are equivalent to NC¹.

Answer 5

The solution of Hilbert's tenth problem by Davis, Matiyasevich, Putnam, and Robinson, showing that the recursively enumerable sets are precisely the Diophantine sets.

(I am reproducing here a blog post, Hindsight, from a couple of years ago, as suggested in the comments.)

From Georg Kreisel's review of The decision problem for exponential diophantine equations, by Martin Davis, Hilary Putnam, and Julia Robinson, Ann. of Math. (2), 74 (3), (1961), 425–436. MR0133227 (24 #A3061).

This paper establishes that every recursively enumerable (r.e.) set can be existentially defined in terms of exponentiation. […] These results are superficially related to Hilbert’s tenth problem on (ordinary, i.e., non-exponential) Diophantine equations. The proof of the authors’ results, though very elegant, does not use recondite facts in the theory of numbers nor in the theory of r.e. sets, and so it is likely that the present result is not closely connected with Hilbert’s tenth problem. Also it is not altogether plausible that all (ordinary) Diophantine problems are uniformly reducible to those in a fixed number of variables of fixed degree, which would be the case if all r.e. sets were Diophantine.

Of course, my favorite quote in relation to the tenth problem is from the Foreword by Martin Davis to Yuri Matiyasevich’s Hilbert’s tenth problem.

During the 1960s I often had occasion to lecture on Hilbert’s Tenth Problem. At that time it was known that the unsolvability would follow from the existence of a single Diophantine equation that satisfied a condition that had been formulated by Julia Robinson. However, it seemed extraordinarily difficult to produce such an equation, and indeed, the prevailing opinion was that one was unlikely to exist. In my lectures, I would emphasize the important consequences that would follow from either a proof or a disproof of the existence of such an equation. Inevitably during the question period I would be asked for my own opinion as to how matters would turn out, and I had my reply ready: “I think that Julia Robinson’s hypothesis is true, and it will be proved by a clever young Russian.”

Answer 6

The Hilbert's program and his "conjecture" about decidability of formal theories. It was formulated in the early 1920s and was pursued by him and his collaborators at the University of Gottingen and elsewhere in the 1920s and 1930s.

"With this new grounding of mathematics – which one can appropriately call a proof theory – I believe to dispose of the foundational questions in mathematics as such once and for all by turning every mathematical statement into a concretely exhibitable and rigorously derivable formula and thereby transferring the whole complex of questions into the domain of pure mathematics."

It is well known that Hilbert's proposals "crashed" (rather quickly [1931]) into Godel's incompleteness theorem.

For a nice overview of the Hilbert's program and later developments see: Richard Zach; Hilbert's Program then and now; Handbook of the Philosophy of Science. Volume 5: Philosophy of Logic; 2006

See also Andrés Caicedo's answer for another aspect of the story: the Hilbert's tenth problem that was solved only in 1970.

Answer 7

In a lecture by Madhu Sudan* he claimed there was some belief that there exists $s > 1/2$ such that $\text{PCP}_{1,s}[ \log n, 3] \subseteq \text{P}$, via semidefinite programming, prior to the proof of Håstad's three bit PCP theorem.

Indeed SDP does show $\text{PCP}_{1,1/2}[ \log n, 3] = \text{P}$, giving a tight bound on the complexity of such PCPs.

(*I found this lecture of Madhu published in "Computational Complexity Theory edited by Rudich/Wigderson")

Answer 8

conjectures range on a spectrum from formal to informal. for example Hilberts famous conjecture about the decidability of mathematics was formalized into a few problems eg Hilberts 10th problem but it was also a more grandiose informal conjecture spanning the whole field. it can also be seen as a proposed research program.

one easy recipe to find such "obituary of dead conjectures" would be to consider the "meta-" statement "[x] conjecture could be proved in my lifetime." mathematics literature is full of such statements/ expectations that turned out to be "false" in the sense of utterly defying expectations about difficulty and accessibility of a proof. a classic one is the Riemann conjecture, open for over ~1½ century. applying this same model to complexity theory is not as easy because complexity theory is a much younger scientific field. however, heres a key example.

the early discovery of the P vs NP problem (now open 4½ decades) had a sort of innocence in that the original investigators did not and could not have imagined how hard or crosscutting the problem would turn out to be. to make this more specific, consider the field of circuit complexity invented in the early 1980s eg by Sipser. this was a research program somewhat like Hilberts mounted in part to attack P vs NP. some of the historical outcome is summarized by Arvind in this abstract/ introduction The computational Complexity Column, BEATCS 106:

The 1980’s was a golden period for Boolean circuit complexity lower bounds. There were major breakthroughs. For example, Razborov’s exponential size lower bound for monotone Boolean circuits computing the Clique function and the Razborov-Smolensky superpolynomial size lower bounds for constant depth circuits with MOD_p gates for prime p. These results made researchers optimistic of progress on big lower bound questions and complexity class separations. However, in the last two decades, this optimism gradually turned into despair. We still do not know how to prove superpolynomial lower bounds for constant-depth circuits with MOD₆ gates for a function computable in exponential time.

there were two key papers that shot down hopes in the field. Razborov had great/ celebrated results on the Clique function but then wrote two opposing papers. one paper showed that Matching, a P-time problem, requires exponential monotone circuits and therefore in some sense the monotone circuit approach to lower bounds was thwarted because of a lack of correspondence in complexity with nonmonotone ("complete") circuits (still not fully understood).

this was expanded on in his famous paper Natural Proofs coauthored with Rudich in which it is shown that all prior circuit lower bounds proofs are subject to a particular pattern which has provable weakness in the sense of conflicting with conjectured lower bounds on hard random number generators from cryptography.

so, to some degree circuits have "fallen from grace". it is still a massive research area but the conventional wisdom, supported by technical results, is that some kind of special as-yet-unknown proof pattern/ structure would be required to get strong results in the area, if actually even possible. in fact similarly one might suggest that even "strong lower bounds in complexity theory" overall are now seen to be extremely difficult, and this was not widely expected/ predicted in the younger days of the field. but on the other hand this then ranks them up there in difficulty/ significance/ importance with the big (open) problems of mathematics.