New answers tagged np-complete
37
Nothing.
Lower bound: Suppose $h(x) = -f(x)$. Then $\sum_x g(x) = 0$, which is trivial to compute. If $\sum_x f(x)$ is NP-hard to compute, then $\sum_x h(x)$ will be too, but $\sum_x g(x)$ will be easy to compute.
Upper bound: Suppose $h(x) = f(x)$. Then $\sum_x g(x) = 2 \sum_x f(x)$, which is as hard as computing $\sum_x f(x)$, which is assumed to be NP-...
0
A special case of set cover problem is able to do this reduction.
Let 2SC be the Set Cover problem restricted to instances where each item appears in at most two sets.
Given instance $\langle U,S={S_1,S_2,\ldots}\rangle$, reduction from 2SC to vertex cover: create an edge for each elements in U where each edge in $S_i$ share a common endpoint $v_i$. Then, U ...
2
Subset-sum illustrates the importance of input encoding in defining NP-complete problems.
Subset-sum for $n$ integers in $[1,k]$ can be solved in $O(nk)$ worst-case time. That's a linear algorithm if the input is encoded in unary. But the problem is NP-complete if you encode the integers in binary, which takes $O(n\log k)$ bits.
The GitHub code that you ...
3
This is not what amortized analysis means: you can not infer the worst case runtime of an algorithm by plotting the actual execution time on larger and larger instances of some specific structure. Sadly, that doesn't prove you have a polynomial-time algorithm. Even when you want to do experimental work, there are other parameters to vary besides the size of ...
0
Let $B$ be a $\mathsf{NP}$-hard problem and $A=\emptyset$. Then $A \le_p B$ (the reduction just maps any instance of $A$ to some fixed "no" instance of $B$). However $A$ cannot be $\mathsf{NP}$-hard since there is no Karp reduction from $\Sigma^* \in \mathsf{NP}$ to $A$.
0
While Tom's answer is correct, I think there is more to be said. For example, there is a finite number of chess positions on an 8x8 board with the 50 moves rules, yet we can sometimes hear statements like "Chess is PSPACE-complete".
In order to study the complexity of such a problem, you have to generalize it, i.e. allow it to have arbitrarily ...
1
I'm not sure how well it'll work, but the idea is simple:
Consider a continuous relaxation of the function
Run projected gradient descent
1.) First, consider a discrete case: let $x_i$ be $1$ if we pick an $i$-th element, and $0$ otherwise. The constraint is $\sum_i x_i \le k$. For each set $S_j$, we want to write a function which is $1$ when all $i \in ...
2
No. Bitcoin mining can be solved in $O(1)$ time. Unfortunately the hidden constant is quite large.
1
I can describe a solution that runs in linear time and is likely to give a solution that is close to optimal, if all of the sets $S_i$ are chosen uniformly at random, and only for the specific parameters you mentioned. The method is easy to describe; explaining why it is likely to be close to optimal is much hairier.
Algorithm
Pick two sets $S_{i_1},S_{i_2}...
0
A problem $L$ is $\text{NP}$-complete if $L$ is in $\text{NP}$, and $L$ is $\text{NP}$-hard (that is, $A\leq_p L$ for all $A\in \text{NP}$ ). Consider the following claims.
Claim 1: if $L$ is $\text{NP}$-complete and $L\in \text{P}$, then $\text{NP} \subseteq \text{P}$ (that is, all problems in $\text{NP}$ can be solved in deterministic polynomial time).
...
1
Your problem is actually in P. First of all, you can assume that no clause contains both a variable and its negation, since such clauses are always satisfied. Suppose that the instance contains $m$ clauses. Then a random assignment will falsify your formula with probability $m/2^{n/2}$. If $m < 2^{n/2}$, then this means that your formula is satisfiable. ...
1
The problem is NP complete.
It is trivially in $NP$ (a certificate is the collection of the $y$ selected subsets of $S$), and it is $NP$-hard since it is the decision version of the Maximum Coverage Problem.
0
We reduce from 3-coloring, following Kráľ, Kratochvíl, Tuza and Woeginger, Complexity of Coloring Graphs without Forbidden Induced Subgraphs. We will need to use a gadget $H$, with the following properties:
$H$ is a 3-colorable triangle-free graph.
There are two vertices $a,b \notin H$, not connected by an edge, such that any 3-coloring of $H$ gives $a,b$ ...
2
Each time you remove a vertex $v$ with degree $<c−1$, the degree of all its neighbours will be reduced by 1, so if any neighbor $u$ gets a degree $<c−1$ after removing $v$, remove $u$ as well; don't stop on $v$. Once you are done you will get what is called the ($c−1$)-core of the graph, which is the induced subgraph where all of its vertices has a ...
0
The problem is NP-hard, so you shouldn't expect any efficient algorithm that will always work. You can look for heuristics, or approximation algorithms, or sometimes-efficient algorithms.
If I had to solve it in practice, probably the first thing I would try would be to use a SAT solver. Introduce a boolean variable $x_v$ for each vertex $v$; then add ...
0
One almost correct reduction looks like: consider the graph $G'$ that is obtained by adding $N$ new vertices to the input graph $G$. Also, add edges that connect every new vertex to all the vertices in $G$. Its not hard to show that $G$ has a clique of size at least $k$ iff $G'$ has a clique of size at least $k+1$. Note that the degree of each new vertex ...
4
I know that NP-complete problems cannot be solved in polynomial time.
We don't know this. This is exactly the P vs NP question. NP-complete problems can be solved in polynomial time iff P=NP.
If P ≠ NP, then all problems in NP cannot be solved in polynomial time.
P is a subset of NP, so some problems in NP can definitely be solved in polynomial time.
...
1
I don't know whether there are any good heuristics, but I can suggest one approach: you could try to use an ILP solver on this task. Introduce zero-or-one variables $x_{i,v}$, $y_{i,u,v,w}$, where $x_{i,v}=1$ means that vertex $v$ is contained in partition $P_i$, and $y_{i,u,v,w}=1$ means that $u,v,w$ are a 3-clique in $P_i$. (Only introduce variables $y_{...
0
The problem you describe is exactly asymmetric TSP. As your reduction shows, asymmetric TSP generalizes the Hamiltonian circuit problem, which is known to be NP-hard.
Usually we consider metric versions of TSP, in which the triangle inequality $c(i,k) \leq c(i,j) + c(j,k)$ holds, and often the TSP instance is symmetric, $c(i,j) = c(j,i)$. Your reduction ...
Top 50 recent answers are included
