Are there good examples of reasonable open problems in TCS that had an 'obvious' solution via application of a theorem found in mathematics probably found a few decades earlier but went unnoticed in TCS until someone provided a footnote with the 'obvious' solution?
Asked
Active
Viewed 154 times
7
-
possibly no significant research results ever have "obvious" solutions, that word hangs up the question some... there is some loose similarity to this question longstanding conjectures later trivially proved by an implication. maybe what you are more interested in is "significant bridge theorems" between TCS/math where areas not thought to be previously connected are connected via a dramatic flourish of applying existing theorems with careful/ detailed/ ingenious insight. – vzn Dec 15 '14 at 22:23
-
There was a time when the internet was not famous! – Turbo Dec 15 '14 at 22:27
-
hm. thinking about it more, simultaneous independent discoveries of important TCS theorems might fit into this question somewhat. ie it is only realized after publication of both papers that the authors have "discovered"/ proved essentially the same thing, with minor variations. one of the biggest examples in CS is the Cook-Levin theorem. also historically Turing completeness fits somewhat into this. – vzn Dec 15 '14 at 22:30
-
1Possible duplicate of Long-Standing Conjectures later trivially proved by an implication – Joshua Grochow Oct 08 '19 at 16:40