Timeline for Reduction problem to another problem
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 9, 2017 at 8:24 | vote | accept | Carol | ||
| Aug 7, 2017 at 21:31 | comment | added | Raphael | The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! | |
| Aug 7, 2017 at 21:31 | comment | added | Raphael | Hint: look at the definition of NP-completeness. It's all there. | |
| Aug 7, 2017 at 21:30 | history | edited | Raphael |
edited tags
|
|
| Aug 7, 2017 at 19:38 | comment | added | Ariel | $f$ is called a reduction from $A$ to $B$ iff $x\in A\iff f(x)\in B$. The righthand side becomes meaningless when $f$ is specified by a NTM, what is $f(x)$? | |
| Aug 7, 2017 at 19:36 | comment | added | rus9384 | @Ariel, a reduction that can be done by NTM. Of course, Karp reduction (and Turing reduction) also is such a reduction. | |
| Aug 7, 2017 at 19:34 | comment | added | Ariel | @rus9384 What is a nondeterministic reduction? | |
| Aug 7, 2017 at 18:39 | answer | added | Kyle Jones | timeline score: 3 | |
| Aug 7, 2017 at 18:21 | comment | added | rus9384 | @miracle173, why am I wrong? Every poly-time deterministic reduction is also poly-time non-deterministic reduction. Reversal is true iff $\mathsf{P = NP}$. | |
| Aug 7, 2017 at 18:06 | history | edited | fade2black | CC BY-SA 3.0 |
added 4 characters in body
|
| Aug 7, 2017 at 17:57 | comment | added | miracle173 | @Carol; 1) search for reduction and complete on this site. 2) $P$ isnt a good name for a problem in this context because $P$ is also used for the complexity class $P$. | |
| Aug 7, 2017 at 17:55 | comment | added | miracle173 | @rus9384 I think you are wrong | |
| Aug 7, 2017 at 17:42 | comment | added | rus9384 | There must be a non-deterministic poly-time reduction. However, I don't know about reductions that use non-determinism. | |
| Aug 7, 2017 at 17:21 | history | asked | Carol | CC BY-SA 3.0 |