<p>Prior to $\mathsf{IP} = \mathsf{PSPACE}$, it was thought possible that even $\mathsf{coNP}$ wasn't contained in $\mathsf{IP}$: in <a href="http://dx.doi.org/10.1016/0020-0190(88)90199-8">Fortnow-Sipser 1988</a> they conjectured this to be the case and gave an oracle relative to which it was true.</p>

CC BY-SA 3.0
2015-10-05T23:17:23.047Z
2015-10-05T23:17:23.047Z
Joshua Grochow
<p>The $\mathsf{3SUM}$-conjecture: That any deterministic algorithm for $\mathsf{3SUM}$ requires $\Omega(n^2)$ time.</p>

<p>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].</p>

<p>[1] Threesomes, Degenerates, and Love Triangles. Allan Grønlund and Seth Pettie. In Foundations of Computer Science (FOCS) 2014, pp. 621-630. <a href="http://arxiv.org/abs/1404.0799">arXiv:1404.0799</a> [cs.DS]</p>

CC BY-SA 3.0
2015-10-08T07:26:19.273Z
How in the world did they get that title past the reviewers?
David Zhang
CC BY-SA 3.0
2015-10-06T01:58:23.523Z
2015-10-06T01:58:23.523Z
Mangara
<p><b>Constant-width branching programs require more than polynomial length to count</b>:  After Furst-Saxe-Sipser and Ajtai in 1981 showed that AC<sup>0</sup> 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 <a href="http://www.sciencedirect.com/science/article/pii/0022000089900378">they are equivalent to NC<sup>1</sup></a>.   </p>

CC BY-SA 3.0
2015-10-06T07:55:46.513Z
2015-10-06T07:55:46.513Z
Paul Beame
<p>The solution of Hilbert's tenth problem by Davis, Matiyasevich, Putnam, and Robinson, showing that the recursively enumerable sets are precisely the Diophantine sets. </p>

<p>(I am reproducing here a <a href="https://andrescaicedo.wordpress.com/2013/08/11/hindsight/">blog post</a>, <em>Hindsight</em>, from a couple of years ago, as suggested in the comments.)</p>

<p>From <a href="https://en.wikipedia.org/wiki/Georg_Kreisel">Georg Kreisel</a>'s review of <em>The decision problem for exponential diophantine equations</em>, by Martin Davis, Hilary Putnam, and Julia Robinson, Ann. of Math. (2), <strong>74 (3)</strong>, (1961), 425–436. <a href="http://www.ams.org/mathscinet-getitem?mr=133227">MR0133227 (24 #A3061)</a>.</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>Of course, my favorite quote in relation to the <a href="https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem">tenth problem</a> is from the Foreword by Martin Davis to Yuri Matiyasevich’s <a href="http://logic.pdmi.ras.ru/~yumat/H10Pbook/"><strong>Hilbert’s tenth problem</strong></a>.</p>

<blockquote>
  <p>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.”</p>
</blockquote>

CC BY-SA 3.0
2015-10-06T04:32:02.643Z
2015-10-06T04:32:02.643Z
Andrés E. Caicedo
<p>$\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).</p>

CC BY-SA 3.0
2015-10-05T22:31:18.973Z
@Arul: Yes. That's an analogy between complexity classes defined by bounding time, and complexity classes defined by bounding space...
Joshua Grochow
CC BY-SA 3.0
2015-10-05T22:42:35.950Z
@Arul: Correct. That's precisely why it's just an analogy...
Joshua Grochow
CC BY-SA 3.0
2015-10-05T20:50:56.303Z
2015-10-05T20:50:56.303Z
Joshua Grochow
<p>The <a href="https://en.wikipedia.org/wiki/Hilbert&#39;s_program" rel="nofollow noreferrer">Hilbert's program</a> 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.</p>

<p><em>"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."</em></p>

<p>It is well known that Hilbert's proposals "crashed" (rather quickly [1931]) into <a href="https://en.wikipedia.org/wiki/G%C3%B6del&#39;s_incompleteness_theorems" rel="nofollow noreferrer">Godel's incompleteness theorem</a>.</p>

<p>For a nice overview of the Hilbert's program and later developments see: <a href="http://people.ucalgary.ca/~rzach/static/hptn.pdf" rel="nofollow noreferrer">Richard Zach; Hilbert's Program then and now; Handbook of the Philosophy of Science. Volume 5: Philosophy of Logic; 2006</a> </p>

<p>See also <a href="https://cstheory.stackexchange.com/a/32724/3247">Andrés Caicedo's answer</a> for another aspect of the story: the Hilbert's tenth problem that was solved only in 1970. </p>

CC BY-SA 3.0
2015-10-06T08:42:41.380Z
2015-10-06T08:51:51.743Z
2017-04-13T12:32:28.080Z
Marzio De Biasi
<p>In a lecture by Madhu Sudan* he claimed there was some belief that there exists $s &gt; 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. </p>

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

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

CC BY-SA 3.0
2015-10-07T11:16:11.180Z
2015-10-07T11:16:11.180Z
Joe Bebel
<p>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.</p>

<p>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.</p>

<p>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 <a href="http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/viewFile/118/132" rel="nofollow">The computational Complexity Column, BEATCS 106</a>:</p>

<blockquote>
  <p>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<sub>p</sub> 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<sub>6</sub> gates for a function computable in exponential
  time.</p>
</blockquote>

<p>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).</p>

<p>this was expanded on in his famous paper <a href="https://en.wikipedia.org/wiki/Natural_proof" rel="nofollow">Natural Proofs</a> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-10-06T20:40:36.350Z
What conjecture are you highlighting?  Also, circuit complexity seems to be both very active and rather successful, for instance Rossman's multiple breakthroughs; see Jukna's authoritative textbook for a more grounded overview of the field.
András Salamon
CC BY-SA 3.0
2015-10-06T20:43:24.333Z
there are multiple interrelated ideas, but eg the "rough" conjecture that circuits in general or some special form (eg monotone) could prove P vs NP or strong lower bounds... it was never exactly strictly formalized but circulates in many (old) circuit theory papers. it is not strictly disproved either, but is heavily revised with 2020 hindsight. the monotone circuit story in particular is a "near reversal".
vzn
CC BY-SA 3.0
2015-10-07T06:13:10.360Z
If you cited some specific references as support for a monotone circuit about-face, then that would be a nice answer. But the above comes across as throwing a lot of words at the wall and hoping some stick; it has nuance but lacks a clear thesis.  In my reading I have not formed the impression that monotone circuits were ever thought to be especially powerful.
András Salamon
CC BY-SA 3.0
2015-10-08T20:41:25.690Z
@AndrásSalamon: I think that view represents the benefit of hindsight. That is, after Razborov's exponential lower bound on monotone circuits for clique, I think there was fairly widespread optimism that much bigger circuit lower bounds (such as $NP \not\subseteq P/poly$) were "right around the corner." (Perhaps not as widespread as the belief that $P neq NP$, but I think widespread enough to be worth mentioning as an answer to this question.)
Joshua Grochow
CC BY-SA 3.0
2015-10-09T08:14:51.937Z
@JoshuaGrochow, I agree, but that is quite different from the tangled thread above.  Perhaps worth posting as an answer?
András Salamon
CC BY-SA 3.0
2015-10-09T15:58:48.747Z
@vzn: Given that this question is CW, would you mind my posting a more succinct answer that just has the item about optimism for circuit lower bounds? I would naturally point to your answer, but I agree with Andras that this one small point out of your larger answer is probably worth highlighting. Or you could do it.
Joshua Grochow
CC BY-SA 3.0
2015-10-09T16:32:32.463Z
@Joshua/ @András thx for interest but the votes indicate its all controversial. dont think a reformulation would help that. feel free to (heavily) edit current answer or add new one, will probably upvote myself if you do, but dont think any further effort is worthwhile :(
vzn
CC BY-SA 3.0
2015-10-06T15:53:54.020Z
2015-10-06T15:53:54.020Z
vzn
<p>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:</p>

<ol>
<li><p><em>Random oracle hypothesis:</em> 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 <a href="http://www.csee.umbc.edu/~chang/papers/roh/">The Random Oracle Hypothesis is False</a>.</p></li>
<li><p><em>Bounded error randomness properly extends the power of polynomial time</em> (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). </p></li>
</ol>

<p>Which are some other conjectures that failed the test of time?</p>

CC BY-SA 3.0
2015-10-05T20:47:22.083Z
Prior to IP=PSPACE, it was even thought possible that $\mathsf{coNP} \not\subseteq \mathsf{IP}$, see [Fortnow-Sipser 1988](http://dx.doi.org/10.1016/0020-0190(88)90199-8). I don't know if this counts as a separate answer with the same resolution, or if it's too similar to your example 1.
Joshua Grochow
CC BY-SA 3.0
2015-10-05T22:37:00.777Z
The Hilbert's program (“... dispose of the foundational questions in mathematics as such once and for all ...” ) and his "conjecture" about decidability of formal theories [~1920], that "crashed" (rather quickly [1931]) into Godel's incompleteness theorem :-)
Marzio De Biasi
CC BY-SA 3.0
2015-10-05T22:43:10.403Z
@MarzioDeBiasi: Sounds like a great answer to me!
Joshua Grochow
CC BY-SA 3.0
2015-10-05T22:54:43.233Z
@JoshuaGrochow Yes, I view the case of co-NP vs. IP a good answer in itself.
Andras Farago
CC BY-SA 3.0
2015-10-05T22:56:10.433Z
@MarzioDeBiasi I also find it a great answer!
Andras Farago
CC BY-SA 3.0
2015-10-05T23:58:25.640Z
In the spirit of Marzio's comment, but in the opposite direction, there is the solution of Hilbert's tenth problem by Davis, Matiyasevich, Putnam, and Robinson, showing that the recursively enumerable sets are precisely the Diophantine sets. The key to this result was showing that exponentiation is Diophantine, thanks to *The decision problem for exponential diophantine equations* by Davis, Putnam, and Robinson.
Andrés E. Caicedo
CC BY-SA 3.0
2015-10-05T23:58:58.413Z
The review of this paper, by Kreisel, reads "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. ...   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." (See also [here](https://andrescaicedo.wordpress.com/2013/08/11/hindsight/).)
Andrés E. Caicedo
CC BY-SA 3.0
2015-10-06T04:14:33.993Z
@AndrésCaicedo: The Davis quote on your linked blog post seems to indicate that this is a perfectly valid answer. I suggest posting it as such, with the Davis quote. (I wasn't aware that people thought it so unlikely.)
Joshua Grochow
CC BY-SA 3.0
2015-10-06T04:33:08.460Z
@Joshua Thanks for the suggestion. It is posted now.
Andrés E. Caicedo
CC BY-SA 3.0
2015-10-06T08:40:27.797Z
Related: [Surprising Results in Complexity](http://cstheory.stackexchange.com/q/276/)
Kaveh
CC BY-SA 3.0
2015-10-06T08:43:04.323Z
Also the post [Surprising Results](http://blog.computationalcomplexity.org/2005/12/surprising-results.html) from Computational Complexity blog.
Kaveh
CC BY-SA 3.0
2015-10-06T16:19:37.853Z
Perhaps this could rather be called an Ossuary, a Crypt, or Obituaries, rather than a singular Obituary.  Presumably the bones of several conjectures are meant to be interned here...
András Salamon
CC BY-SA 3.0
2015-10-07T16:33:42.707Z
@AndrásSalamon Thank you, I corrected it to Obituaries. First I thought that "obituary" could be used in singular with a collective meaning,  like "depository," but I may have been wrong. English is a rich language, but not my native... :-)
Andras Farago
<cc.complexity-theory><ds.algorithms>
Obituaries of dead conjectures
Andras Farago
# Obituaries of dead conjectures

(Asked by: username_0 on 2015-10-05)

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](http://www.csee.umbc.edu/~chang/papers/roh/).
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?

**Tags:** cc.complexity-theory, ds.algorithms

> **Comments:**
> **username_1**: Prior to IP=PSPACE, it was even thought possible that $\mathsf{coNP} \not\subseteq \mathsf{IP}$, see [Fortnow-Sipser 1988](http://dx.doi.org/10.1016/0020-0190(88)90199-8). I don't know if this counts as a separate answer with the same resolution, or if it's too similar to your example 1.  
> **username_2**: The Hilbert's program (“... dispose of the foundational questions in mathematics as such once and for all ...” ) and his "conjecture" about decidability of formal theories [~1920], that "crashed" (rather quickly [1931]) into Godel's incompleteness theorem :-)  
> **username_1**: @MarzioDeBiasi: Sounds like a great answer to me!  
> **username_0**: @JoshuaGrochow Yes, I view the case of co-NP vs. IP a good answer in itself.  
> **username_0**: @MarzioDeBiasi I also find it a great answer!  
> **username_3**: In the spirit of Marzio's comment, but in the opposite direction, there is the solution of Hilbert's tenth problem by Davis, Matiyasevich, Putnam, and Robinson, showing that the recursively enumerable sets are precisely the Diophantine sets. The key to this result was showing that exponentiation is Diophantine, thanks to *The decision problem for exponential diophantine equations* by Davis, Putnam, and Robinson.  
> **username_3**: The review of this paper, by Kreisel, reads "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. ...   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." (See also [here](https://andrescaicedo.wordpress.com/2013/08/11/hindsight/).)  
> **username_1**: @AndrésCaicedo: The Davis quote on your linked blog post seems to indicate that this is a perfectly valid answer. I suggest posting it as such, with the Davis quote. (I wasn't aware that people thought it so unlikely.)  
> **username_3**: @Joshua Thanks for the suggestion. It is posted now.  
> **username_4**: Related: [Surprising Results in Complexity](http://cstheory.stackexchange.com/q/276/)  
> **username_4**: Also the post [Surprising Results](http://blog.computationalcomplexity.org/2005/12/surprising-results.html) from Computational Complexity blog.  
> **username_5**: Perhaps this could rather be called an Ossuary, a Crypt, or Obituaries, rather than a singular Obituary.  Presumably the bones of several conjectures are meant to be interned here...  
> **username_0**: @AndrásSalamon Thank you, I corrected it to Obituaries. First I thought that "obituary" could be used in singular with a collective meaning,  like "depository," but I may have been wrong. English is a rich language, but not my native... :-)  

---

## 8 answers

### Answer by username_1 on 2015-10-05. Score: 24

$\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).

> **Comments:**
> **username_1**: @Arul: Yes. That's an analogy between complexity classes defined by bounding time, and complexity classes defined by bounding space...  
> **username_1**: @Arul: Correct. That's precisely why it's just an analogy...  

---

### Answer by username_1 on 2015-10-05. Score: 21

Prior to $\mathsf{IP} = \mathsf{PSPACE}$, it was thought possible that even $\mathsf{coNP}$ wasn't contained in $\mathsf{IP}$: in [Fortnow-Sipser 1988](http://dx.doi.org/10.1016/0020-0190(88)90199-8) they conjectured this to be the case and gave an oracle relative to which it was true.


---

### Answer by username_6 on 2015-10-06. Score: 20

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](http://arxiv.org/abs/1404.0799) [cs.DS]

> **Comments:**
> **username_7**: How in the world did they get that title past the reviewers?  

---

### Answer by username_8 on 2015-10-06. Score: 18

**Constant-width branching programs require more than polynomial length to count**: After Furst-Saxe-Sipser and Ajtai in 1981 showed that AC0 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 NC1](http://www.sciencedirect.com/science/article/pii/0022000089900378).


---

### Answer by username_3 on 2015-10-06. Score: 17

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](https://andrescaicedo.wordpress.com/2013/08/11/hindsight/), *Hindsight*, from a couple of years ago, as suggested in the comments.)

From [Georg Kreisel](https://en.wikipedia.org/wiki/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)](http://www.ams.org/mathscinet-getitem?mr=133227).

> 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](https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem) is from the Foreword by Martin Davis to Yuri Matiyasevich’s [**Hilbert’s tenth problem**](http://logic.pdmi.ras.ru/~yumat/H10Pbook/).

> 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 by username_2 on 2015-10-06. Score: 9

The [Hilbert's program](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorems).

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](http://people.ucalgary.ca/~rzach/static/hptn.pdf)

See also [Andrés Caicedo's answer](https://cstheory.stackexchange.com/a/32724/3247) for another aspect of the story: the Hilbert's tenth problem that was solved only in 1970.


---

### Answer by username_9 on 2015-10-07. Score: 8

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 by username_10 on 2015-10-06. Score: 1

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](http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/viewFile/118/132):

> 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 MODp 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 MOD6 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](https://en.wikipedia.org/wiki/Natural_proof) 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.

> **Comments:**
> **username_5**: What conjecture are you highlighting?  Also, circuit complexity seems to be both very active and rather successful, for instance Rossman's multiple breakthroughs; see Jukna's authoritative textbook for a more grounded overview of the field.  
> **username_10**: there are multiple interrelated ideas, but eg the "rough" conjecture that circuits in general or some special form (eg monotone) could prove P vs NP or strong lower bounds... it was never exactly strictly formalized but circulates in many (old) circuit theory papers. it is not strictly disproved either, but is heavily revised with 2020 hindsight. the monotone circuit story in particular is a "near reversal".  
> **username_5**: If you cited some specific references as support for a monotone circuit about-face, then that would be a nice answer. But the above comes across as throwing a lot of words at the wall and hoping some stick; it has nuance but lacks a clear thesis.  In my reading I have not formed the impression that monotone circuits were ever thought to be especially powerful.  
> **username_1**: @AndrásSalamon: I think that view represents the benefit of hindsight. That is, after Razborov's exponential lower bound on monotone circuits for clique, I think there was fairly widespread optimism that much bigger circuit lower bounds (such as $NP \not\subseteq P/poly$) were "right around the corner." (Perhaps not as widespread as the belief that $P neq NP$, but I think widespread enough to be worth mentioning as an answer to this question.)  
> **username_5**: @JoshuaGrochow, I agree, but that is quite different from the tangled thread above.  Perhaps worth posting as an answer?  
> **username_1**: @username_10: Given that this question is CW, would you mind my posting a more succinct answer that just has the item about optimism for circuit lower bounds? I would naturally point to your answer, but I agree with Andras that this one small point out of your larger answer is probably worth highlighting. Or you could do it.  
> **username_10**: @Joshua/ @András thx for interest but the votes indicate its all controversial. dont think a reformulation would help that. feel free to (heavily) edit current answer or add new one, will probably upvote myself if you do, but dont think any further effort is worthwhile :(  

---

