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

CC BY-SA 3.0
2014-12-15T22:23:20.373Z
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](http://cstheory.stackexchange.com/questions/27265/long-standing-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
CC BY-SA 3.0
2014-12-15T22:27:49.330Z
There was a time when the internet was not famous!
Turbo
CC BY-SA 3.0
2014-12-15T22:30:32.403Z
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](http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem). also historically [Turing completeness](http://en.wikipedia.org/wiki/Turing_completeness) fits somewhat into this.
vzn
CC BY-SA 4.0
2019-10-08T16:40:27.467Z
Possible duplicate of [Long-Standing Conjectures later trivially proved by an implication](https://cstheory.stackexchange.com/questions/27265/long-standing-conjectures-later-trivially-proved-by-an-implication)
Joshua Grochow
<big-list><big-picture><open-problem><survey>
Examples of open problems solved through application of a theorem already known
Turbo
# Examples of open problems solved through application of a theorem already known

(Asked by: username_0 on 2014-12-14)

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?

**Tags:** big-list, big-picture, open-problem, survey
> **Comments:**
> **username_1**: 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](http://cstheory.stackexchange.com/questions/27265/long-standing-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.  
> **username_0**: There was a time when the internet was not famous!  
> **username_1**: 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](http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem). also historically [Turing completeness](http://en.wikipedia.org/wiki/Turing_completeness) fits somewhat into this.  
> **username_2**: Possible duplicate of [Long-Standing Conjectures later trivially proved by an implication](https://cstheory.stackexchange.com/questions/27265/long-standing-conjectures-later-trivially-proved-by-an-implication)  

---

## 0 answers

