The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
2
votes
1answer
4k views

Difference between NP-Hard and NP-Complete [closed]

Can someone please summarize the exact difference between NP-Complete and NP-Hard problems in simple language? Wiki and my standard books aren't exactly helping.
4
votes
1answer
420 views

Better approximation for special case of 3-hitting set

I have a question based on 3-Hitting Set problem. In this problem, we are given a universal set U of size n and a set of subsets S such that $\forall $ s $\in$ S |s|<=3. FOr this problem, Integer ...
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 ...
8
votes
1answer
483 views

Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments

Given a tournament $T$ where $S_1$ and $S_2$ be two acyclic sub-tournament of $T$. Is the following problem NP-Complete: Finding a maximum acyclic sub-tournament $S$, which is subset of $S_1 \cup ...
12
votes
4answers
1k views

Directed NP-hard problems on DAGs

Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This ...
16
votes
1answer
702 views

Completeness and Context-Sensitive Languages.

I'm interested in two questions regarding context-sensitive languages (CSL) and completeness: Is there a notion of completeness for CSL, and which languages are complete? Are there natural CSL that ...
41
votes
4answers
9k 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). ...
20
votes
4answers
1k views

Positive topological ordering, take 3

Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix? This question is motivated by this problem: Positive topological ordering ...
6
votes
0answers
208 views

Further question on hardness of node partitioning under shortest path constraint

This question first appeared at Hardness of node partitioning under shortest path constraint and I restate it here Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \...
24
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, ...
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 ? (...
3
votes
2answers
332 views

Complexity of the Hamiltonian Subcycle problem

The problem is as follows: Given a graph $G$, find a (vertex) disjoint set of cycles $C$ on $G$ such that every vertex is visited by a cycle exactly once. My question is then: what is the ...
15
votes
2answers
941 views

NP-hard problems on expander graphs?

In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT? , Nati Linial posed the following open problem: Which $NP$-hard computational problem on graph remain hard when ...
4
votes
1answer
591 views

Hardness of node partitioning under shortest path constraint

Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in R$ (negative weight is possible). A label $l(i)$ is associated with each node $i \in V$. How to assign $k$ (or less)...
10
votes
1answer
401 views

What are the complexities of the following SAT subsets ?

Assume $P \neq NP$ Let use the following notation ${}^ia$ for tetration (ie. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$). |x| is the size of the instance x. Let L be ...
5
votes
1answer
340 views

Complexity of finding vectors with optimal projection?

Input: a set $T$ of vectors $v_i=(x_i,y_i,z_i)$. Where $x_i,y_i,z_i$ are integers. Output: a subset of vectors $v_1,v_2,...,v_n$ with vector addition $m=\sum v_i$ such that the projection of $m$ on ...
5
votes
2answers
319 views

Use of Lagrangian dual information to prove optimalitiy of a solution : Any example?

Can anyone please tell me what is Lagrangian Dual Information and how can it be used to prove the optimality of a solution? I'm talking about the solution to NP-Complete problems. Is it something that ...
1
vote
1answer
1k views

Removing all but a few cycles in a graph

Let problem $S$ be defined as Given undirected graph $G$ and a set of cycles $C_1,C_2, \ldots, C_n$ in G, find minimum number of vertices that need to be deleted to remove all cycles in the ...
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 ...
10
votes
2answers
1k views

NP-complete variants of undecidable problems?

Examples of bounded $NP$-complete variants of undecidable sets: Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps} Bounded Tiling={ $(T, 1^t)$| there is ...
10
votes
1answer
417 views

Hardness of constrained star system problem?

A star system is a family $F$ of n subsets of n-elements set $S$. A star system is graphical if there is some graph $G(V,E)$ such that $F$ is the family of vertex neighborhoods in $G$. It is $NP$-...
3
votes
2answers
3k views

Using decision version of TSP to solve optimization version

Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP. This is not a homework assignment, but of general interest. I have been trying ...
14
votes
1answer
882 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
7
votes
4answers
793 views

A relaxed Steiner Tree Problem

Given a weighted graph $G(V,E,w)$ where $w$ is the weight function on edges and a subset of vertices $S\subseteq Q$ called terminals, a Steiner Tree is a connected subgraph which connects all vertices ...
5
votes
1answer
428 views

Comparing $\mathbf{NP}$ and $\mathbf{E}$

We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$. The complexity zoo states that $\mathbf{E}$ does not equal $\mathbf{NP}$, and cites the following ...
7
votes
1answer
3k views

Simple reduction to unbounded knapsack?

Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited ...
0
votes
2answers
907 views

Where is the error in the following P != NP pseudo-proof ?

Here is a necessarily wrong proof of $P \neq NP$ as it relativizes, but I can't find the error : Le $U$ be a universal Turing machine, whose inputs are restricted to Turing machines accepting ...
11
votes
1answer
388 views

Computation of max H-free sets

In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question,...
8
votes
4answers
2k views

Complexity of marriage matching problem?

Suppose you have $n$ males and $n$ females. Each person has $m$ attributes. Each person indicates a set of attributes that a possible candidate should have. A matching is a set of pairs. Each pair ...
6
votes
3answers
610 views

In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.

Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament. I have doubt whether the problem mentioned can be solved in polynomial ...
20
votes
3answers
641 views

Is it hard to find optimal addition chains?

An addition chain is a sequence of positive integers $(x_1, x_2, \dots, x_n)$ where $x_1 = 1$ and each index $i\ge 2$, we have $x_i = x_j + x_k$ for some indices $1\le j,k < i$. The length of the ...
13
votes
2answers
350 views

H-free partition

This is a question inspired by the H-free cut problem. Given a graph, a partition of its vertex set $V$ into $r$ parts $V_1, V_2, \ldots, V_r$ is $H$-free if $G[V_i]$ does not induce a copy of $H$ for ...
21
votes
1answer
340 views

Consensus clustering using set union

I've already posted this question a while ago on MathOverflow, but to the best of my knowledge it is still open, so I'm reposting it here in the hope that someone might have heard of it. Problem ...
22
votes
9answers
957 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 ...
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 ...
23
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 ...
11
votes
6answers
2k views

Do many-one reductions and Turing reductions define the same class NPC

I wonder if NPC classes defined by many-one reductions and Turing reductions are equal. Edit: Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class ...
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 ...
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. ...
3
votes
4answers
2k views

Why is P vs. NP so hard? [closed]

Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important? Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem? Why is it so hard? All I'm looking for is the hindrances ...
11
votes
2answers
3k views

Any fast algorithm for minimum cost feedback arc set problem?

In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set. If each edge is associated with a weight $w$, the minimum cost ...
18
votes
4answers
1k views

“All-different hypergraph coloring” - known problem?

I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
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$ ...
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 ...
25
votes
2answers
4k views

What are the consequences of factoring being NP-complete?

Are there any references covering this?
5
votes
1answer
21k views

Is integer factorization an NP-complete problem? [duplicate]

Possible Duplicate: What are the consequences of factoring being NP-complete? What notable reference works have covered this?
39
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?
128
votes
28answers
19k 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? ...
17
votes
2answers
625 views

H-free cut problem

Suppose you are given a connected, simple, undirected graph H. The H-free cut problem is defined as follows: Given a simple, undirected graph G, is there a cut (partition of vertices into two ...
8
votes
3answers
3k views

Is Deolalikar's 2010 proof that $P \ne NP$ correct?

There was recently a claimed proof that $P \ne NP$. Not long after its publication there were raised some issues with this proof. So ... is the proof correct or not ? (Please only answer this if you ...