New answers tagged np-complete
3
The objective function $f$ (to minimize) is not completely formalized in the question. It is written that the groups should "sum to as close to a target as possible", so it seems natural to assume that $f$ is $0$ if the sum of the elements in each group is equal to the target, and greater than $0$ otherwise.
Two examples of such functions are the maximum ...
4
The reduction is possible.
I'll give a reduction of minimum feedback arc set to minimum feedback arc set with maximum outdegree two. The basic idea is that if node $i$ has outdegree $d_{i}$, we make $d_{i}$ copies of node $i$. We add new nodes representing edges so that edges can still be cut in one operation.
Say the graph we want to solve minimum ...
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 ...
1
You reduce Independent set to Vertex cover. You want to say that the vertex cover is atleast as hard as Independent set. One could way to remember is you are using a subroutine for vertex cover to solve Independent set. Since Independent set is Np-C you know you know the subroutine you used can't be polynomial. If you do the other way around using a ...
1
Your first guess is correct. You misinterpreted however the meaning of reductions. When we prove the hardness of a problem $A$ by a reduction from $B$, we aim to reduce $B$ to $A$ and hence, given an instance $I$ of $B$, we want to build an instance $I'$ of $A$ such that $I$ is a yes-instance if and only if $I'$ is.
Now by reducing set cover to your problem,...
1
Can you color a planar graph with k colours?
k = 0, k = 1: Trivial.
k = 2: Easy peasy.
k = 3: NP-complete.
k = 4: Very, very hard proof that the answer is always "Yes".
k = 5, 6, 7, etc. : Easy proof that the answer is always "Yes".
2
Yes. See the notion of an approximation-preserving reduction.
1
NP doesn’t look at how hard it is to find a certificate (in this case a factor), just at how hard it is to test a certificate that claims to prove the answer is “yes”.
So it doesn’t matter how hard it is to find a factor, just that given a factor of an n-bit number, you can easily verify that it is a factor in $O(n^2)$. Or a bit faster with more effort. So ...
2
Let $d_1,\ldots,d_n\geq 2$ be positive integers and let $T \in \Bbb R^{d_1\times \ldots \times d_n}$ be a tensor (hypermatrix) of order $n$.
SVD: The singular value decomposition (understood as canonical polyadic decomposition for $n\geq 3$) is NP-hard for $n\geq 3$ (see [1]). Similarly computing the rank of $T$ over any finite field is NP-complete, and it ...
4
There are many problems like this listed in Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David S. Johnson. For instance,
[ND14] Graph Partitioning: NP-hard for $K\geq3$ and in P for $K=2$.
[SP3] Set Packing: NP- hard even for all $c\in C$ with $|c|\leq 3$ but in P if for all $c\in C$ have $|c|\leq 2$.
[SP4] Set ...
2
No. Intuitively, the problem gets harder if we take out the restrictions on the input values, since the restricted instances are a subset of the instances of the general problem. However, the article says, even if you introduce this restriction the problem does not get easier and it is still strongly NP-complete.
On the other hand, exhaustive search is not ...
0
It's almost always the case that problem sizes are expressed as a function of the length of the input, so a number n would be taken to be $\log n$ in length. For example, your verification would be in poly time if it ran in $O(\log^k n)$ time for some integer $k$.
4
One more example is $k$-partitioning problem, where given a set $A$ of $n$ numbers where $n$ is a multiple of $k$, the goal is to find a partition of $A$ into $k$-tuples, such that the numbers in each tuple sum up to zero.
More specifically, given a set $A$ of $m \cdot k$ elements. The goal is to partition $A$ into $m$ tuples $(a_{i1}, \dots a_{ik})$ for $i ...
5
In graph coloring you are looking for a partitioning of the vertex set into independent sets. Now, there are many arguably well-known similarly behaving (i.e., easy for $k=2$, hard for $k \geq 3$) problems where instead you want to find a partition into $k$ sets which could be (i) independent dominating, (ii) dominating, (iii) total nearly perfect, (iv) ...
2
You can reduce numerical 3-dimensional 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_k\},Y=\{y_1,\ldots,y_k\},Z=\{z_1,\ldots,z_k\}$, you can construct $k$ bins with capacities $b-x_1+M+M^2,\ldots,b-x_k+M+M^2$, and $2k$ balls with sizes $y_1+M,\ldots,y_k+M, z_1+M^2,\ldots,z_k+M^2$, ...
2
We will reduce Vertex Cover to Edge Dominating Set and complete the proof. Given an instance of the decision version of vertex cover problem $I(G,k)$, we construct $G'$ by adding $nk+k$ new edges to $G$, where $n$ is the number of vertices in $G$:
add $k$ new vertices;
add an edge between each of these new vertices and each vertex in $G$, totally $nk$ ...
2
This is NP-hard by reduction from 3-dimensional matching (3DM): turn each triple $\{a, b, c\}$ into a valid pair $\{a, b\}$ of balls for bin $c$, and add a large number of balls that don't belong to any valid pairs (so that if they go in a bin, they must be the sole occupant). The optimal solution will then hold $k+m$ balls ($k$ bins with 2 balls each and $m-...
1
These problems can be solved efficiently.
For Problem 2, both [1] and [2] prove that the problem is solvable in $O(n^{2.5} / \log n)$ time. That is, this is the variant of Hamiltonian path with specific start and end vertices.
For Problem 1, i.e., when the input graph is a semicomplete bipartite digraph, it appears (see [3]) that a Hamiltonian path is ...
4
Yes. You can solve this in polynomial time. The same strategy as in Are SAT problems with at most one false clause NP-complete? works.
Let $\varphi$ denote the CNF formula you care about, and $n$ the number of variables in $\varphi$. Let $A_{i,j}$ denote the number of truth assignments that do not satisfy clauses $i$ or $j$ of $\varphi$, let $A_i$ denote ...
-2
It depends on the availability of data...
If you store the relaitonships between the data rather than trying to compute at runtime then it is an o1 operation with massive storage requirements...
Otherwise arbitrarily hard..
2
This problem is clearly NP-hard since it is a generalization of many NP-hard problems. The most obvious one is the maximum clique problem, i.e. finding a clique of the maximum size in a graph. The decision version of this problem is a special case of your problem where you set $t$ equal to one. (See below for the hardness-proof).
Further reading.
Other ...
2
However, if one of the coordinates has exponentially many bits with respect to the input, then is this considered as a exponential-time checking? Or it is still polynomial-time with respect to the length of the solution?
The length of the solution/certificate must be polynomial in the size of the original instance. Therefore, if the certificate/solution can ...
Top 50 recent answers are included
