Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with np
Search options answers only
not deleted
user 472
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
3
votes
Sequence to explore the complexity of the NP problem
Could you simulate that in an NP-hardness proof? Or you might start by building an NP-hardness proof from a "nearby problem" that has similar characteristics. …
- 22.8k
2
votes
Relationship between complexity classes W[1] and NP?
But ETH is stronger than P not equal to NP, so its falsification doesn't settle P = NP (but of course, if true, ETH would imply that P is not equal to NP). …
- 22.8k
5
votes
Accepted
Has anyone seen a NP graph problem like this before?
The problem is NP-complete even on planar graphs according to [1], but I don't know about its complexity on partial grids. …
- 22.8k
4
votes
Can someone explain why the MAX-CUT problem is in NP?
The certificate is a coloring of the vertices into red and blue (i.e., a partition into two sets). Given such a certificate, you can iterate through all the edges and count the number of edges whose e …
- 22.8k
4
votes
Accepted
Prove the red blue separation problem is NP-complete
MSP is NP-hard. The hardness was first shown by Eades and Rappaport by a reduction from TSP, see [1], Section 2 for the reduction.
[1] Eades, Peter, and David Rappaport. …
- 22.8k
5
votes
Problems that are NP but polynomial on graphs of bounded treewidth
Typically, for many "local problems" such as $\mathsf{Vertex Cover}$ or $\mathsf{IndependentSet}$ (meaning a solution can be verified by checking the neighborhood of each vertex), standard dynamic pro …
- 22.8k
5
votes
Is there any strategy to brute force search?
The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely …
- 22.8k
1
vote
Negative simple path NP-Complete
Let $G=(V,E)$ be an instance of Hamiltonian $st$-path. Construct an instance of negative $st$-path $G'$ such that $G' = G$ with a new vertex $t'$ and the edge $tt'$ added. Set the weight of $tt'$ to $ …
- 22.8k
4
votes
Is there any NP-hard problem which was proven to be solved in polynomial time or at least cl...
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. …
- 22.8k
17
votes
What does the 2 in a 2-approximation algorithm mean?
Typically, we use $\alpha < 1$ for maximization problems, and $\alpha > 1$ for minimization problems, where $\alpha$ is the approximation guarantee. So, a $2$-approximation algorithm returns a solutio …
- 22.8k