# Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

589 questions
Filter by
Sorted by
Tagged with
977 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 ...
592 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)...
422 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 ...
341 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 ...
323 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 ...
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 ...
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 ...
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 ...
435 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$-...
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 ...
901 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 ...
803 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 ...
431 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 ...
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 ...
914 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 ...
422 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,...
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 ...
671 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 ...
671 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 ...
370 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 ...
359 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 ...
986 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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
3k 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 ...
4k 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 ...
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 ...
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$ ...
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 ...
4k views

### What are the consequences of factoring being NP-complete?

Are there any references covering this?
25k 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?
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?
20k 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? ...
653 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 ...
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 ...