Timeline for Obituaries of dead conjectures
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 9, 2015 at 16:32 | comment | added | vzn | @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 :( | |
| Oct 9, 2015 at 15:58 | comment | added | Joshua Grochow | @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. | |
| Oct 9, 2015 at 8:14 | comment | added | András Salamon | @JoshuaGrochow, I agree, but that is quite different from the tangled thread above. Perhaps worth posting as an answer? | |
| Oct 8, 2015 at 20:41 | comment | added | Joshua Grochow | @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.) | |
| Oct 7, 2015 at 6:13 | comment | added | András Salamon | 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. | |
| Oct 6, 2015 at 20:43 | comment | added | vzn | 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". | |
| Oct 6, 2015 at 20:40 | comment | added | András Salamon | 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. | |
| S Oct 6, 2015 at 15:53 | history | answered | vzn | CC BY-SA 3.0 | |
| S Oct 6, 2015 at 15:53 | history | made wiki | Post Made Community Wiki by vzn |