New answers tagged np
0
Regarding the problem of visiting as many vertices/edges as possible without using any edge twice: one can look at this problem as the problem of finding an Eulerian subgraph with a maximum number of vertices/edges. Or alternatively, as the problem of deleting a minimum number of vertices/edges so as to make a graph Eulerian.
You might be interested in the ...
2
The other answers are correct, but f I may add an observation: it seems like you are conflating classes of problems and particular instances. There are a number of instances that can be solved in polynomial time in classes that are NP-hard in general. For instance, Boolean satisfiability is NP-hard in general, since it reduces to 3SAT. However, there are a ...
5
If the answer to the first question were to be yes, then $P=NP$, as stated in nir shahar's answer. This has not been done.
"The easiest NP hard problem"
However you next asked if any NP-hard problems have been solved in close to polynomial time, for which you might love to learn about what has been called "The easiest NP hard problem" ...
4
Strictly speaking, as the other answers explain, no. A polynomial-time algorithm for an NP-hard problem is not known nor expected to exist. But I think your underlying question is whether or not there are examples of natural NP-hard problems that are, in some sense, easier to solve than some other NP-hard problems.
There are several flavors in which you can ...
10
By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no.
However, its possible to think instead of solving the problems fully, to approximate a solution, or to solve them randomly. There are attempts at attacking from those points of view, but they are not perfect at all. ...
2
The dynamic programming algorithm goes over all subsets of $[3k]$ whose size is a multiple of 3, in nondecreasing order of size. For each such non-empty subset, it goes over all $O(n^3)$ triplets of vertices, and for each one, it performs a single table look-up. Therefore the running time is $O^*(2^{3k} n^3)$, where $O^*$ hides $\operatorname{poly}(k)$ ...
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 ...
0
Start by initializing a boolean array $T$ with indices from $0$ to $b$, inclusive. $T_0$ starts as true (because you can always achieve a sum of 0) and the rest of the array starts as false.
For each value $a_i$, we update the array by going though each value $x$ where $x+a_i\leq b$, and setting $T_{x+a_i}$ to true only if $T_x$ is true.
Essentially, at any ...
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 ...
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.
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 ...
1
Note that $\#P\in FP^{PP}$ follows from a simple binary search. Given some non-deterministic machine $M$, the language $\{(x,k) |\#M(x)\ge k\}$, where $\#M(x)$ is the number of accepting paths on input $x$, is in PP (you can change the constant in the definition of PP to any FP function). Thus, using a PP oracle we can count the number of accepting paths via ...
Top 50 recent answers are included
