New answers tagged np
3
votes
I would like to know what are the directions to work on if I want to prove that $NP=coNP$?
There are no directions that are likely to be accessible to an amateur. The problem is believed to be extremely hard. No one knows of any directions that are believed to be very promising. Instead, ...
D.W.♦
- 150k
3
votes
Accepted
If $NP^{NP} = NP$, then the polynomial hierarchy collapses to it's first level. How to prove it?
Prove that $\Sigma_i^P = NP$ for $i \ge 2$ by induction on $i$.
The base case is $i=2$ and is trivial since, by hypothesis, $\Sigma_2^P = NP^{NP} = NP$. For the inductive step, suppose that $\Sigma_i^...
- 26.1k
1
vote
3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation
When you want to prove a reduction is true (such as this from 3-Dimensional Matching to Subset Sum), what you want to show is that you can take any input for 3-Dimensional Matching and turn it into an ...
- 692
0
votes
Accepted
How to show a language is in NP?
You have already figured out that $f^{-1}(x)$ can be used as a potential NP certificate. You are just missing the crucial part in the definition of NP.
You don't have to compute the certificate, you ...
- 38
0
votes
How to show a language is in NP?
The value $f(x)$ is a polynomial length certificate for the language, since it has the same size as $x$, and can be checked in polynomial time by verifying that $f^{-1}(f(x)) = x$ and that $f(x) < ...
- 213
0
votes
How is the Subset Sum Problem NP-Complete?
The subset sum problem can easily be solved in polynomial time in the number of items, and the sizes of the items. However, to be in NP, the solution must be in polynomial time in the problem size. ...
- 27.1k
0
votes
Is One Way TSP NP-Complete?
Take your "one way" problem. Add another city X, make the distance from start to X = 0, make the distance from X to any other city d which is longer than the sum of all other distances, then ...
- 27.1k
2
votes
Accepted
Is One Way TSP NP-Complete?
The answer depends on how you define "One Way TSP".
If the One Way TSP problem asks to compute the tour itself, then it cannot possibly be NP-complete since it is not a decision problem, and ...
- 26.1k
4
votes
Accepted
Why is 3-co-SAT not in P?
co-SAT is not asking whether there exists an unsatisfying assignment, it is asking if every assignment evaluates to false.
- 14.3k
Top 50 recent answers are included