google-deepmind / google-deepmind/formal-conjectures
The P vs BPP question
- Dominant language
- Lean
- Stars
- 1.3k
- Forks
- 485
- Avg merge
- 1d 20h
- Merged PRs (30d)
- 327
Description
### What is the conjecture
The P vs. BPP problem/conjecture asks/states that the complexity class [BPP](https://en.wikipedia.org/wiki/BPP_(complexity)) (the set of decision problems decidable in polynomial time with bounded error) is equal to P.
### Prerequisites needed
We've already formalized some complexity theoretic concepts in service of P vs. NP, so there is not much more that needs to be done to add this conjecture besides defining BPP itself. I have a branch [here](https://en.wikipedia.org/wiki/BPP_(complexity)) which indicates that this can be done in only a few lines.
### [AMS categories](https://github.com/google-deepmind/formal-conjectures/labels?q=ams-)
* ams-68
### Choose either option
- [x] I plan on adding this conjecture to the repository
- [ ] This issue is up for grabs: I would like to see this conjecture added by somebody else
Contributor guide
Assessment
This issue has not been assessed yet.