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.

551 questions
Filter by
Sorted by
Tagged with
576 views

### Exact exponential-time algorithms for 0-1 programming

Are there known algorithms for the following problem that beat the naive algorithm? Input: A system $Ax \le b$ of $m$ linear inequalities. Output: A feasible solution $x^*\in \{0,1 \}^n$ if ...
624 views

684 views

### Set optimization problem - is it np-complete?

Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective ...
762 views

### Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?

There are some NP-Complete problems ($\mathsf{SAT}$, $\mathsf{SUBSETSUM}$, etc.) known to be in $\mathsf{DSPACE(n)}$. What about the sub-linear spaces? Is there any known NP-Complete (or NP-...
849 views

### Does every Turing-recognizable undecidable language have a NP-complete subset?

Does every Turing-recognizable undecidable language have a NP-complete subset? The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
397 views

### Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton

Problem statement : Let $M$ be a (potentially nondeterministic) pushdown automaton and let $\cal A$ be its input alphabet. Is there a word $w \in \cal A^*$ s. t. $|w| \leq k$ that is accepted by $M$ ?...
348 views

### Is the backup problem NP-complete?

Is the following decision problem NP-complete: Let $G$ be an undirected graph and $b \le c$ two integers. Is it possible to select for every vertex of $G$ exactly $b$ different neighbors ...
673 views

### Proof that sparsest cut is NP-hard

Everywhere that I read about the sparsest cut problem, it only says that the problem is known to be NP-hard. Where can I find a proof of this? Which known NP-hard problem reduces to the sparsest cut ...
373 views

### Exact exponential-time algorithms for 0-1 programs with nonnegative data

Are there known algorithms for the following problem that beat the naive algorithm? Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers. Output: an ...
689 views

### Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

Suppose P != NP. We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there ...
145 views

### Best known asymptotic PCP sizes / 3-SAT

What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am ...
675 views

### NP-Hardness of a special case of orthogonal packing problem

Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used ...
227 views

126 views

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 ...
1k views

### P vs NP: Instructive example of when Brute Force search can be avoided

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
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 ...
358 views

### Complexity of the $(3,2)_s$ SAT problem?

Let define the $(3,2)_s$ SAT problem : Given $F_3$, a satisfiable 3-CNF formula, and $F_2$, a 2-CNF formula ($F_3$ and $F_2$ are defined on the same variables). Is $F_3 \wedge F_2$ satisfiable? What ...
650 views

### What is complexity of this max-edge subgraph problem?

While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below: Given a connected undirected graph, finding a maximum-...
425 views

### Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio ...
624 views

### Minimum Triangle Covers

Given a graph $G$, what is the minimum number of edges of $G$ that we need to delete to make the graph triangle free? To my untrained eye, this appears to be a difficult problem. Is this problem ...
366 views

### A partition problem in which some numbers may be cut

In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard. However,...
254 views

### NP-hardness on Cayley graphs

What is known about complexity of NP-hard problems on Cayley graphs? Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input ...
2k views

### What are good approximation algorithms for the subset sum problem so far?

By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.
549 views

### Fitting minimum number of rectangles of width/height 1 into a 2D grid

Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied and you need to put the minimum number of non-overlapping rectangles of any size w x h where ...