# Questions tagged [complexity-classes]

Computational complexity classes and their relations

670 questions
Filter by
Sorted by
Tagged with
121k views

### Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct? Also on topic: where else (on the internet) is its correctness being discussed? Note: the focus of this question text has ...
• 1,679
4k views

### What is the complexity class most closely associated with what the human mind can accomplish quickly?

This question is something I've wondered about for a while. When people describe the P vs. NP problem, they often compare the class NP to creativity. They note that composing a Mozart-quality ...
4k views

### Can one amplify P=NP beyond P=PH?

In Descriptive Complexity, Immerman has Corollary 7.23. The following conditions are equivalent: 1. P = NP. 2. Over finite, ordered structures, FO(LFP) = SO. This can be thought of as "...
• 18.9k
2k views

• 2,151
1k views

• 11.3k
1k views

### Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
• 231
1k views

### Can typed lambda calculi express *all* algorithms below a given complexity?

I know that the complexity of most varieties of typed lambda calculi without the Y combinator primitive is bounded, i.e. only functions of bounded complexity can be expressed, with the bound becoming ...
• 8,911
1k views

### What are the compelling reasons for believing $L\neq P$?

What are the compelling reasons for believing $L\neq P$? L is the class of log-space algorithms with pointers to the input. Suppose L=P for the moment. What would a log-space algorithm for a P-...
• 239