# Questions tagged [np-hard]

decision problems that are at least as hard as NP-complete problems

528 questions
Filter by
Sorted by
Tagged with
13 views

### NP-Complete reductionTrue/False question explanation

Why is the above statement true? my understanding is: (1)3SAT reduces to X implies X is NP-complete or harder. (2)Set Cover reduces to X implies X is neither NP-Complete nor harder. This ...
53 views

### An NP-hard problem reduces to its complement?

I found this statement in a true/false test section: Could someone explain in laymans why this is a true statement? My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must ...
129 views

### What is wrong with the following $P$ problem?

Our teacher gave us the following statement and we were wondering what is wrong with it. Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$, we cannot check ...
2k views

### A problem in NP but not NP-complete?

Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.
24 views

54 views

### Clique-or-almost reduction to clique

I saw the posted question here about a direct reduction from near-clique to clique. Clique-or-almost is like near-clique but with the option for a complete clique of size $k$, I mean that perhaps an ...
81 views

### Is GAP NP-hard with at most two balls per bins?

The generalized assignment problem (GAP)  is given by: Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and ...
47 views

### Multiple Knapsack Problem with Set of Admissible Balls

We have $m$ bins and $n$ balls. Each bin $i=1,2,\ldots,m$ can contain at most two balls (not any two balls but two balls from some specific set), see 3. Each ball $j=1,2,\ldots,n$ can be put into ...
65 views

### Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?

Let us say we have $m$ bins and $n$ balls. Every bin $i$ has capacity $c_i$ which is the number of balls that can be put into bin $i$. We have $c_i\geq1$ for all $i$. For each bin $i$, there is a ...
44 views

### Which is the most similar NP classic problem, if any exists, to this one?

Consider a given set $W = \{w_1, w_2,...,w_N\}$ of weights, such that $\sum_{i=1}^N w_i = 0$. Consider the given set of mutually different elements $A=\{a_1,a_2,...,a_M\}$ with $M\leq N$. Consider the ...
30 views

### Knapsack up to the heaviest item

There are $n$ items with weights $w_1,\ldots,w_n$ and values $v_1,\ldots,v_n$. There is a knapsack with capacity $W$. A subset of items is called feasible up to heaviest item if, once the heaviest ...
252 views

### If a problem is not in NP, prove that every NP problem can be efficiently reduced to it

I understand that an NP-hard problem is a problem X such that any problem in NP can be reduced to X in polynomial time. Does there exist a problem that is hard to solve but problems in NP cannot be ...
67 views

### Hitting Set Problem with non-minimal Greedy Algorithm

The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
36 views

### complexity of a variant of the subset sum problem

We have a set of positive integers $N=\{a_1,...,a_n\}$, we want to select a subset $N'$ of $N$ with maximum total sum of integers such that this sum should not exceed a given integer $B$. What is the ...
29 views

### What is the name of this problem (the dual of the asymmetric k-center problem)

I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse. In this ...
121 views

### How to prove NP-hardness from scratch?

I am working on a problem of whose complexity is unknown. By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use. Finally, I have decided ...
226 views

### If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time. Now I am learning that a convex optimization problem can ...
86 views

### Algorithm to find a simple path with maximum weight less than a constant in DAG

Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should ...