# Tag Info

## Hot answers tagged np-complete

5

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 ...

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) ...

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 ...

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 ... 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 Although the shape of the problem instance is constrained, we still have total control over the polyominos themselves in any problem instance we decide to create, and we can get there by carefully messing with them. A gangly polyomino in a double-width problem instance Given the initial$a \times b$problem instance, create a new instance of size$(2a+1) \...

3

P is a subset of NP, so any P language is NP as well. Also note that any deterministic machine is a non-deterministic machine where the image of the transitions function has always a size exactly equal to one. This implies that from each configuration you get a unique following configuration.

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 ...

2

Yes. See the notion of an approximation-preserving reduction.

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 ...

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 ...

2

Here is an $n^{O(k)}$-time SAT algorithm: try all (at most $n^k$) ways how to select one literal from each clause, and accept whenever the selection is such that it does not include any contradictory pair (i.e., a literal and its negation). So, if $k$ is substantially smaller than $n$, you get a subexponential algorithm, and you should not be able to prove ...

2

I understand how this proves that it is NP-complete It isn't a "proof" by any means. It's an example of how a reduction might work, but it hasn't been stated as a formal proof. From your example, it looks like the algorithm/proof is as follows: The universe consists of $3$ types of elements: one element $x_i$ for every variable $i$, one element $C_j$ for ...

2

Let us consider the following decision version of your first problem: Given a SAT instance, does its multilinear representation have a term of degree at most $d$? I claim that this is the case iff the SAT instance has a satisfying assignment with at most $d$ ones. Indeed, suppose first that $m$ is an inclusion-minimal term in the multilinear ...

2

Here is a reduction from the Hamiltonian path. Given a graph $G=(V,E)$. Add a vertex $v_0$ to the graph and connect it to all vertices in the graph. Set $t(v_0)=2$. Set $t(u) = 1$ for all $u \neq v_0$. Claim. The previous reduction is correct. Try to prove it formally as an exercise. Edit. Here is a brief proof of correctness. We have to prove that the ...

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.

1

You can prove this by a reduction from the Hitting Set problem (which is NP-Complete): Given a base set $U$, a family $F = \{S_1,\ldots,S_\ell\}$ of subsets of $U$ and an integer $q$, decide if there exists a set $H$ of size at most $q$ which intersects every set in $F$ (this is called a hitting set). So suppose given an instance of the Hitting Set ...

1

Take any infinite NP-complete language $L$. The language $L$ has uncountably many subsets, and particular there is some uncomputable subset $Q \subseteq L$. Since $Q$ is uncomputable, in particular it is not in NP, and so not NP-complete. You can also try your example. Let $L$ consist of all pairs $(G,k)$ such that $G$ can be colored using at most $k$ ...

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

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 ...

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".

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 ...

Only top voted, non community-wiki answers of a minimum length are eligible