New answers tagged np-hard
1
The set $S$ consists of $12$ numbers. Hence it has $2^{12} = 4096$ subsets.
You can write a computer program that goes over all subsets, sums each of them, and determines whether the sum is $492$, in which case it prints the subset.
0
This is an answer to your first problem. For all $x \in S$, there are only two possibilities $x$ belong to some solution or $x$ does not belong to any solution. In order to check if $x$ belong to some solution, you need to call the given oracle on the updated value $t-x$. There will be two possibilities, one after calling the oracle the answer is no then ...
0
Set the size of the bag to the value you are trying to reach $t$. For each element $x \in S$ add one item to the set having both its weight and value equal to $x$. The claim is the $(S, t)$ is a yes instance of the subset sums problem if and only if the optimal value of the bag is equal to $t$ (why?).
2
This question can be reduced to the exact cover problem which is NP-Complete. A typical method for solving the exact cover problem is known as Algorithm X.
Consider the set of choices you have:
For each tetris piece of $4$ units, you can select an orientation and a location to place it on the board. For each choice, the piece will cover $4$ squares on the ...
1
The accepted answer is incorrect: assuming $P\not=NP$ there are lots of problems incomparable with $SAT$, hence neither $NP$ nor $NP$-hard.
Here's an overkill generalization of this fact:
Suppose $X\not\in P$. Then there is some $Y$ such that $Y$ is incomparable with $X$ under polynomial-time-Turing reducibility (hence a fortiori Karp reducibility).
(So ...
4
If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case.
If, however, $P \neq NP$, then there are languages which are neither in NP nor NP-hard.
For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this ...
3
Let $S, k$ be a given instance of the subset sums problem. The goal is to build an equivalent instance of your problem (let us call it the pens arrangement problem). In the subsetsums problem, we are looking for a subset of the given set that sums up to $k$. So it is intuitive to set $G$ to $k$ and set the lengths of the pens to be the numbers in the given ...
1
If I understand correctly you only have a problem when the graph $G = (V,E)$ of the vertex-cover instance has isolated vertices. In this case you can transform $G$ into a related graph $G' = (V \cup \{x,y \}, E')$ by adding a two new vertices $x$ and $y$ such that $x$ and $y$ are connected to each other by an edge, and there is an edge between $x$ and each ...
4
The restriction $m < 2n$ does not help to solve the problem in polynomial time. Note that any 3-dimensional matching instance can be polynomially reduced into an instance with $m < 2n$ by adding $m$ elements to the sets $X$, $Y$ and $Z$ and $m$ hyperedges to connect these new elements. The resulting instance has $n' = n + m$ and $m' = 2m$, so $m' < ...
0
I think there is a greedy way to solve this.
First, note that the $m$ $a_i$ values of triplets should be the $m$ largest values of $S$.
Then for the $2 m$ remaining values. Follow the decreasing $a_i$ and select the pair ($a_j$, $a_k$) among the remaining values to minimize $D = a_i-a_j-a_k$ respecting $D \ge 1$.
If you cannot there is no solution. This ...
2
You can reduce Numeric 3D Matching (N3DM) to your problem.
Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\{x_1,\ldots,x_m\},Y=\{y_1,\ldots,y_m\},Z=\{z_1,\ldots,z_m\}$, construct $2m$ elements $x_1+2M,\ldots,x_m+2M,M-y_1,\ldots,M-y_m$ and $m$ values $b-z_1+M,\ldots,b-z_m+M$ for your problem, where $M$ is a very large number. Now ...
9
Yes, and this holds even for structured graphs. Indeed, every planar graph is 5-colorable (in fact even 4-colorable by the Four color theorem), but it is NP-complete to decide if a planar graph can be colored in 3 colors.
0
It's at least as hard as the "Traveling Salesman" problem, that is NP complete: TSP asks whether a salesman can visit n towns while travelling a distance ≤ K. Take the special case of one worker, who can do n jobs in a day if and only he travels a distance ≤ K, then the question "can the single available worker do all jobs in one day" is equivalent to TSP. ...
Top 50 recent answers are included
