Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
233
votes
11answers
115k 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 ...
128
votes
28answers
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? ...
66
votes
7answers
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....
59
votes
12answers
2k 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, ...
54
votes
4answers
22k 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? ...
46
votes
20answers
7k 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 ...
45
votes
3answers
3k 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 ...
41
votes
4answers
8k 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). ...
39
votes
3answers
3k views

Is the integer factorization problem harder than RSA factorization: $n = pq$?

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 $...
38
votes
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?
38
votes
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 ...
36
votes
3answers
2k views

Techniques for showing that problem is in hardness “limbo”

Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this ...
34
votes
14answers
6k views

Everyday encounters with NP-complete problems

Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap. ...
33
votes
2answers
3k views

Reference for NP-hardness of 3-colouring?

I have a historical question. I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard. The tempting answer ...
30
votes
6answers
2k views

Is there a natural problem on the naturals that is NP-complete?

Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there ...
29
votes
2answers
2k views

Can you identify the sum of two permutations in polynomial time?

There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question: Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ ...
28
votes
2answers
2k views

A category of NP-complete problems?

Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, ...
28
votes
2answers
1k views

When does “X is NP-complete” imply “#X is #P-complete”?

Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version. Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"? Of course the existence ...
28
votes
1answer
1k views

Functions that are Not Efficiently Computable but Learnable

We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable"...
27
votes
2answers
1k views

Ladner's Theorem vs. Schaefer's Theorem

While reading the article "Is it Time to Declare Victory in Counting Complexity?" over at the "Godel's Lost Letter and P=NP" blog, they mentioned the dichotomy for CSP's. After some link following, ...
27
votes
2answers
1k views

Is it possible to find if a sequence exists in polynomial time in the following problem?

I've been thinking about the following problem for a time, and I haven't found a polynomial solution for it. Only brute-fource. I've been trying to reduce an NP-Complete problem into it too with no ...
27
votes
3answers
1k views

Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1

Given an $m$ by $n$ binary matrix $M$ (entries are $0$ or $1$), the problem is to determine if there exists two binary vectors $v_1 \ne v_2$ such that $Mv_1 = Mv_2$ (all operations performed over $\...
26
votes
4answers
2k views

Bounded-cardinality bounded-frequency set cover: hardness of approximation

Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets. Example: the case $k = 4$ ...
26
votes
3answers
885 views

Did “Where the really hard problems are” hold up? What are current ideas on the subject?

I found this paper to be very interesting. To summarize: it discusses why in practice you rarely find a worst-case instance of a NP-complete problem. The idea in the article is that instances usually ...
26
votes
3answers
2k views

Is it NP-hard to play international draughts correctly?

Is the following problem NP-hard? Given a board configuration for $n\times n$ international draughts, find a single legal move. The corresponding problem for $n\times n$ American checkers (aka ...
25
votes
5answers
2k views

Verifying unique solutions of SAT

Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ? What is the complexity of this problem ? (...
25
votes
2answers
3k views

What are the consequences of factoring being NP-complete?

Are there any references covering this?
25
votes
1answer
712 views

Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct ...
25
votes
1answer
1k views

An edge partitioning problem on cubic graphs

Has the complexity of the following problem been studied? Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$ Question: is there a partition of $E$ into $|E|/3$ parts of size $...
24
votes
6answers
2k views

Are there NP-complete problems with polynomial expected time solutions?

Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)? If not, are there problems for ...
24
votes
3answers
2k views

Hardness of approximation - additive error

There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
23
votes
5answers
2k views

Packing rectangles into convex polygons but without rotations

I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps. In my problem you are not allowed to rotate the ...
23
votes
2answers
3k views

Hamiltonicity of k-regular graphs

It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, ...
23
votes
1answer
656 views

Is it still open to determine the complexity of computing the treewidth of planar graphs?

For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-...
23
votes
1answer
1k views

I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle)

It is known that Hamiltonian (Ham for short) Cycle is NP-complete and that Planar Ham Cycle is NP-Complete. The proof for Planar Ham Cycle is not from Ham Cycle. Is there a nice gadget that will, ...
23
votes
2answers
3k 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. ...
22
votes
10answers
2k views

Problems that are easy on unweighted graphs, but hard for weighted graphs

Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), ...
22
votes
9answers
952 views

Reductions from the book.

This is along the lines of "Algorithms from the Book". Although reductions are algorithms as well, I thought it doubtful that one would think of a reduction in response to the question about ...
22
votes
2answers
2k views

Are there any hard instances of 3-SAT when the clauses can only use literals that are “nearby” each other?

Let the variables be $x_1 , x_2 , x_3 ... x_n$. The distance between two variables is defined as $d(x_a , x_b) = |a-b|$. The distance between two literals is the distance between the corresponding ...
22
votes
2answers
527 views

Relation between hardness of recognition of a graph class and forbidden subgraph characterization

I'm considering graph classes that can be characterized by forbidden subgraphs. If a graph class has a finite set of forbidden subgraphs, then there is a trivial polynomial time recognition algorithm ...
22
votes
2answers
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 ...
22
votes
1answer
630 views

Does NP-hardness imply P-hardness?

If a problem is NP-hard (using polynomial time reductions), does that imply that it is P-hard (using log space or NC reductions)? It seems intuitive that if it is as hard as any problem in NP that it ...
22
votes
1answer
542 views

Is there a problem that is easy for cubic graph but hard for graphs with maximum degree 3?

Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, ...
22
votes
1answer
2k views

Tardos Function Counterexample to Blum's $P\neq NP$ Claim

In this thread, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6. Theorem 6: Let $f \in \mathcal{B}_n$ be any ...
22
votes
2answers
487 views

Testing whether letters can be scheduled to achieve a word in a regular language

I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each ...
21
votes
4answers
1k views

DNA-algorithms and NP-completeness

What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they ...
21
votes
4answers
822 views

Problems that are counter-intuitively solvable in practice?

Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in ...
21
votes
1answer
901 views

For which k is PLANAR NAE k-SAT in P?

The Not All Equal $k$-SAT problem (NAE $k$-SAT), given a set $C$ of clauses over a set $X$ of boolean variables such that each clause contains at most $k$ literals, asks whether there exists a truth ...
21
votes
1answer
2k views

Computational complexity of the 3-partition problem with distinct numbers

This question is related to an answer I posted in response to another question. The 3-partition problem is the following problem: Instance: Positive integers a1, …, an, where n=3m and the sum of the ...
21
votes
2answers
929 views

$NP$-completeness of recognizing the difference of two permutations

Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two ...