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 answers only
not deleted
user 95
A reduction is the transformation of one problem into another problem. A example of using a reduction would be to be to show if a problem P is undecidable. This would be achieved by transforming or performing a reduction of a decision problem $P$ into an undecidable problem. If this can be achieved then we have shown that this problem P is undecidable.
9
votes
Accepted
Reducing sorting to max-flow
It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow pr …
- 51.2k
13
votes
Accepted
Is intersection of $k \ge 3$ graphic matroids in P?
I think it is still NP-complete, by a reduction from Hamiltonian paths in bipartite graphs with two degree-one vertices and all other vertices having degree three. (This is just the same as finding Ha …
- 51.2k
16
votes
Accepted
Natural CLIQUE to k-Color reduction
Given a graph $G$ and a number $k$, such that you want to know whether $G$ contains a $k$-clique, let n be the number of vertices in $G$. We construct another graph $H$, such that $H$ is $n$-colorable …
- 51.2k
9
votes
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which...
Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. B …
- 51.2k
4
votes
Accepted
Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical...
A lower bound of approximately $\log_2 n$ still follows for arbitrary 3-regular graphs, based simply on the fact that there are at most $3\times 2^i$ different paths of length $i$ from any given star …
- 51.2k