google-deepmind / google-deepmind/formal-conjectures

Tracking targets in theoretical computer science

Open
#677 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.