# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

732 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,689
25k 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? ...
42k views

### Why is 2SAT in P?

I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...
• 1,205
5k 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....
• 4,700
3k views

### Parameterized complexity from P to NP-hard and back again

I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is non-monotonic in $k$. Most problems (in my experience) have a single phase transition, ...
• 2,799
9k views

### NP-hard problems on trees

Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
• 10.6k
14k views

### Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses). ...
• 1,336
5k views

### An NP-complete variant of factoring.

Arora and Barak's book presents factoring as the following problem: $\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$ They add, further ...
• 3,946
7k 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?
• 1,668
4k views

6k views

### Natural CLIQUE to k-Color reduction

There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. ...
1k views

• 9,269
1k views

### How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about ...
• 2,035