New answers tagged np-complete
0
$(3)\Rightarrow (1)$ should just be a consequence of the definition of $\textsf{NP}$-completeness.
For $(1)\Rightarrow (3)$, you can use the fact that there exists a function $f$, computable in polynomial time, such that $u\in X \Leftrightarrow f(u) \in Z$. Now to decide if $u\in X$, you can compute $f(u)$, and then decide nondeterministically if $f(u)\in Z$....
1
The key reason we need $w_{uv}$ is because not every dominating set is necessarily a vertex cover, but $w_{uv}$ "patches" that up.
In particular, assume isolated vertices can be ignored. Then every vertex cover is a dominating set, but not every dominating set is a vertex cover. Hence, if we tried to do the reduction without adding $w_{uv}$, then ...
3
Suppose you have a graph $G$ of order $n$. $G$ has a simple path of length $\geq n - 1$ if and only if $G$ has a hamiltonian path.
1
The subset sum problem is quite different from your problem: Given a list of integers and a target sum $S$, it asks if there is a subset of the list that sums to $S$. No "compression", lossy or not. Any lossy technique will (by definition) tend to miss the target (because it works with an approximation). And we are looking for an exact solution, ...
2
No. Your argument is not valid; it doesn't prove NP-completeness. You have shown that an ILP solver can be used to solve your problem. But an ILP solver can be used to solve easy problems, too, so it doesn't rule out the possibility that your problem might be easy (solvable in polynomial time). The reduction needs to go the other way. I suggest studying ...
1
This was an examination paper question for Computability and Complexity, as the deadline has now passed, I am able to answer:
The basic answer to this is that it is quite literally, base 2, 3 and base 6.
If my answer itself was correct, you can see in the table we must have the second half of the answer to contain only "3" values, that is to say, ...
0
You can easily define NP-hard optimisation problems: We call a decision problem D NP-hard if any decision problem in NP can be reduced to D in polynomial time. And we can use the same definition for any problem P: P is NP-hard if any decision problem in NP can be reduced to P in polynomial time.
The problem is defining something analogous to NP. If we have a ...
1
Ok, so the short answer to this question seems to be a "yes, but it grows quickly in size". You can view the bloom filters for each tuple element as vectors of bits. In that case, their tensor product will be a "bloom filter" for the cartesian product, where projection can be done by taking partial traces.
The downside of this is that the ...
0
Nope. Bloom filters don't support those operations.
0
You need to look at every individual optimisation problem. Typically you want a “solution” which maximises the value v, while a decision problem would be “is there a solution with a value >= k”
The question is: if you can solve the decision problem, repeatedly, does that allow you to solve the optimisation problem? Usually it lets you solve “what is the ...
0
For the relation between decision and optimization (search) problems, take a peek at Bellare and Goldwasser's The Complexity of Decision versus Search, SIAM Journal of Computing 23(1), feb 1994. In a nutshell: If the decision problem is NP-complete, the search problem is hard too, and can be solved calling the decision problem's solver a polynomial number of ...
3
An $n^k$ prover implies that the set $\{\left(\varphi,1^n\right)|\text{$\varphi$ has a proof of length $\le n$}\}$ is in $P$, since we can simply run the prover for $n^k$ steps and check whether it yields a valid proof.
It remains to show that this language is NP complete. This follows from a straightforward reduction from SAT. Given a CNF $\varphi$ over the ...
2
It is NP-Hard as others have said, but... sometimes there is an easier way to solve it. You can do a Lagrangian relaxation to essentially remove the NP-hardness solve that problem, and then use that as an initial guess for the original problem. Pekny and Miller essentially did something like to for the Asymmetric Traveling Salesman problem. They reduced it ...
2
The special case where $v=0$ and $Y=\{\frac12\sum_{i=1}^m x_i\}$ is the partition problem, which is NP-complete.
1
Let $G$ be a graph with $2n$ vertices, and choose any node $v$. The edges touching $v$ have weight $n$, and all other edges have weight $-1$. Note that any Hamiltonian cycle in $G$ will have two edges touching $v$ (which add up to $2n$) and $2n-2$ edges of weight $-1$, so the total weight of the cycle is exactly $2$.
Therefore, if $G$ has a hamiltonian cycle,...
0
If $k$ is a fixed known value and does not depend on the graph, then I doubt it would be possible to do it efficiently:
Verifying if a graph has a cycle of size $k$ can be done by checking all potential paths of size $k$ and verify if one is indeed a cycle. Since there are at most $\begin{pmatrix}n\\k\end{pmatrix}(k-1)! = O(n^k)$ such path in a graph of ...
1
Let $\langle S, k \rangle$ be an instance of subset sum, where $S=\{a_1, a_2, \dots, a_n\}$. Construct an $0$-$1$-integer program with $n$ binary variables $x_1, \dots, x_n$ and the following constraints:
$$
\begin{align}
a_1x_1+a_2 x_2+ \dots+a_n x_n &\le k \\
-a_1x_1-a_2 x_2 - \dots-a_n x_n &\le -k
\end{align}
$$
Or, in matrix form:
$A =
\begin{...
18
This problem (more formally its decision version) is NP-complete.
NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be NP hard.
In the JSP, we have $n$ jobs $J_1, J_2, ..., J_n$. Within each job there is a set of operations $O_1, O_2, ..., O_n$ which need to be processed in a ...
6
Thanks to "user2357112 supports Monica" for pointing out issues! Now fixed.
Let's formulate the decision problem form of this problem, which I'll call Tree Scheduling (TS):
Given a number $k$, and a rooted tree with
tasks $t_1, \dots, t_n$ for vertices, each having some integer duration $l_i$ and requiring some resource $r_i$ from a set $S$ of ...
14
What you are describing is a planning and scheduling problem. Kautz and Selman pioneered the use of Boolean satisfiability and SAT solvers to attack such problems in the early 1990's. SATPLAN, STRIPS, and PDDL are good search terms for further research. There seem to be several planner implementations that take world descriptions written in STRIPS and ...
3
I think there is an easy reduction from Knapsack.
Knapsack:
Input: a list of couples (value, weight) $\{(v_1, w_1), …, (v_n,w_n)\}$, a maximum weight $W$, a target value $V$
Question: is there a subset $S \subset [\![1, n]\!]$ such that $\sum\limits_{i\in S} v_i \geq V$ and $\sum\limits_{i\in S} w_i \leq W$
Now given an input of knapsack, let's construct ...
2
Recognizing that a path is a Hamiltonian path is easy. Finding one in the first place may be hard (the number of candidates is large).
The defining property of problems in NP is that verifying a solution is "easy" (in P). Your problem is one part of verifying a solution of a Hamiltonian path problem. (You also have to verify that the path is a ...
3
You are correct that $\emptyset\in NP$, since we already know that $\emptyset$ can be decided in constant time (a TM that immediately rejects), and $DTIME(O(1))\subseteq P\subseteq NP$.
But $\emptyset$ is not NP-complete, regardless of whether $P=NP$. Indeed, by definition, a NP-complete language $A$ is such that every language $B \in NP$ admits a Karp ...
4
I don't know precisely how Bob works, but let's talk about clause learning.
Suppose you have a set of variable assignments, $A$, say $x_1 = 0$, $x_2 = 1$, $x_3 = 0$. This is a single clause in disjunctive normal form:
$$A = \neg x_1 \wedge x_2 \wedge \neg x_3$$
The negation of this set of assignments is a single clause in conjunctive normal form:
$$\neg A = ...
1
There is no general rule that they necessarily need to be NP-complete in general.
For the specific examples you list, I expect the answer will be that each of those specific examples are NP-complete, but I haven't tried to prove or verify that; that's just speculation.
3
It is not clear what is your question, but I will guess that it is "what is my mistake in my proof of $P = NP$?"
In addition to the fact that the algorithm does not guarantee to find the minimal path (because the algorithm cant deterministicaly choose the endMem nodes), the number of possible $\log n$-walks given $\log n$ nodes is not polynomial: $(...
2
1. if P=NP does each of the problems on the left reduce to the easy problem (in P) in its immediate right?
If P=NP then every problem on the left is in P, and trivially polynomially equivalent to every problem on the right. There is no special formal correspondence between the pairs of problems in each row of the table. The authors probably chose informally ...
Top 50 recent answers are included
