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 reductions
Search options not deleted
user 62634
In computability and complexity, finding mappings between problems that allow solving one problem using a solution of another one. For reduction in programming language theory (e.g. beta-reduction), see [lambda-calculus] or [term-rewriting].
1
vote
1
answer
602
views
Concrete example of Vertex Cover to Subset Sum reduction
In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line …
- 229
0
votes
How is the Longest Path Problem NP complete?
I agree with @Kyle Jones; and the 'iff' part in the proof looks little fishy to me.
For the NP-Hard part, you may refer to my answer here https://cs.stackexchange.com/a/137129/62634 - I've tried to pr …
- 229
0
votes
3
answers
193
views
How Reduction works in proving NP-Hard?
A problem $X$ is $NP$-Hard if for all $Y \in NP$, $Y \leq_P X$. Further, if a problem $Z$ is $NP$-Complete, and $Z \leq_P X$, then I can prove (rather mechanically) that $X$ is $NP$-Hard.
I also fo …
- 229
0
votes
1
answer
150
views
A doubt on converting NOT gate to CNF formula
For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$.
My expectation …
- 229
3
votes
How to prove NP-hardness of a longest-path problem?
Suppose we have a solution to the longest path problem, longest-path, in which given a graph G, and an integer k, we need to decide if G has any (simple) path of k edges. Then to solve the Hamiltonian …
- 229