# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,540 questions
114k 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 ...
18k views

### Problems Between P and NPC

Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...
15k views

### What kind of mathematical background is needed for complexity theory?

I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
4k views

### Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

Currently, solving either a $NP$-complete problem or a $PSPACE$-complete problem is infeasible in the general case for large inputs. However, both are solvable in exponential time and polynomial space....
4k views

1k views

This is a cross-post from math.stackexchange. Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $... 7answers 5k views ### Many-one reductions vs. Turing reductions to define NPC Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions? 5answers 1k views ### Is there a logic without induction that captures much of P? The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of ... 3answers 8k views ### Is optimally solving the n×n×n Rubik's Cube NP-hard? Consider the obvious$n\times n\times n$generalization of the Rubik's Cube. Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time ... 6answers 2k views ### Geometric problems that are NP-complete in$R^3$but tractable in$R^2$? A number of geometric problems are easy when considered in$R^1$, but are NP-complete in$R^d$for$d\geq2$(including one of my favourite problems, unit disk cover). Does anyone know of a problem ... 4answers 3k views ### Is$PH \subseteq PP$? We know that the first level of the polynomial hierarchy (i.e. NP and co-NP) is in PP, and that$PP \subseteq PSPACE$. We also know from Toda's Theorem that$PH \subseteq P^{PP}$. Do we know whether$...
The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...