Incoming links: NP (complexity)
BQP Updated 2025-07-16
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!
Chomsky hierarchy Updated 2025-07-16
This is the classic result of formal language theory, but there is too much slack between context free and context sensitive, which is PSPACE (larger than NP!).
By Noam Chomsky.
A good summary table that opens up each category much more can be seen e.g. at the bottom of en.wikipedia.org/wiki/Automata_theory under the summary thingy at the bottom entitled "Automata theory: formal languages and formal grammars".
NP-complete Updated 2025-07-16