google-deepmind / google-deepmind/formal-conjectures

The P vs BPP question

Open
#5,175 0 comments 0 reactions 1 assignee Claimed by @BoltonBailey View on GitHub
new conjecture
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

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.