google-deepmind / google-deepmind/formal-conjectures
Tracking targets in theoretical computer science
- Dominant language
- Lean
- Stars
- 1.3k
- Forks
- 485
- Avg merge
- 1d 20h
- Merged PRs (30d)
- 328
Description
The field of theoretical computer science is particularly rich in its use of conjectures. Wikipedia lists [a number of these conjectures and open problems](https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science). I am putting forward this issue to track some of these that I think would be best suited to inclusion in formal-conjectures, in terms of their importance and ease of formalization.
- [x] P ?= NP (#1120)
- [x] NP ?= co-NP (#1120)
- [ ] [P ?= BPP problem](https://en.wikipedia.org/wiki/P_%3D_BPP_problem) (#5175)
- [ ] [exponential time hypothesis](https://en.wikipedia.org/wiki/Exponential_time_hypothesis) (ETH)
- [ ] The strong exponential time hypothesis
- [ ] Existence of one-way functions
- [x] Is Integer Factorization in P? (#4796)
- [ ] Is Graph Isomorphism in P?
Contributor guide
Assessment
This issue has not been assessed yet.