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?

  • $\begingroup$ 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. $\endgroup$
    – vzn
    Dec 15, 2014 at 22:23
  • $\begingroup$ There was a time when the internet was not famous! $\endgroup$
    – Turbo
    Dec 15, 2014 at 22:27
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Dec 15, 2014 at 22:30
  • 1
    $\begingroup$ Possible duplicate of Long-Standing Conjectures later trivially proved by an implication $\endgroup$ Oct 8, 2019 at 16:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.