TODO clear example of the computational problem that it solves.
Interesting because of the Cook-Levin theorem: if only a single NP-complete problem were in P, then all NP-complete problems would also be P!
We all know the answer for this: either false or independent.
University of Cambridge students, CanTabBridgeans.
@cirosantilli/_file/python/typing_cheat/python/typing_cheat/protocol_empty.py Updated 2025-02-26 +Created 1970-01-01
P for quantum computing!
Heck, we know nothing about this class yet related to non quantum classes!
- conjectured not to intersect with NP-complete, because if it were, all NP-complete problems could be solved efficiently on quantum computers, and none has been found so far as of 2020.
- conjectured to be larger than P, but we don't have a single algorithm provenly there:
- it is believed that the NP complete ones can't be solved
- if they were neither NP-complete nor P, it would imply P != NP
- we just don't know if it is even contained inside NP!
Unlisted articles are being shown, click here to show only listed articles.