Timeline for Turing and Many one reductions in computability versus complexity
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 24, 2020 at 0:14 | review | Suggested edits | |||
| Nov 24, 2020 at 13:19 | |||||
| May 7, 2016 at 14:21 | vote | accept | Turbo | ||
| May 7, 2016 at 13:05 | history | undeleted |
Joel David Hamkins Todd Trimble |
||
| May 7, 2016 at 12:29 | history | deleted | Turbo | via Vote | |
| May 7, 2016 at 12:18 | answer | added | Joel David Hamkins | timeline score: 5 | |
| May 7, 2016 at 11:46 | comment | added | Turbo | @JoelDavidHamkins No what is it that that makes their distinguishability non-obvious in complexity theory? What gives away when we replace total computable $f$ by polynomial $f$? How much more strength minimally one should add to $f$ to preserve distinguishability with current know-how? What barriers we encounter when we weaken $f$? May be when $f$ is weakened from total computability we really do not have any distinction between Turing and many-one reduction (if so then what is that computable threshold for $f$)? | |
| May 7, 2016 at 11:44 | comment | added | Joel David Hamkins | Yes, they are very different in computability theory. Is that question what you are specifically asking about? If so, please edit your question to ask a more specific question more clearly. | |
| May 7, 2016 at 11:43 | comment | added | Turbo | @JoelDavidHamkins also is my observation right? Turing reductions have been proven distinct from many-one reductions in computability theory correct? | |
| May 7, 2016 at 11:42 | comment | added | Joel David Hamkins | I think there is a deep question in this vicinity (and I wasn't the down-voter). There is an analogy between the reduction concepts of computability theory, which have been very successful and which have led to a clarifying theory with many results, and the reduction concepts of complexity theory, which is a theory where so many interesting questions, it seems, are still open. The deep question concerns the high-level explanation, if any, for this disanalogous situation in the results, when the basic analogy seems sound. | |
| May 7, 2016 at 11:36 | comment | added | Turbo | @JoelDavidHamkins Is there any possibility of something interesting in my post? | |
| May 7, 2016 at 11:25 | history | undeleted | Turbo | ||
| May 7, 2016 at 11:25 | history | deleted | Turbo | via Vote | |
| May 7, 2016 at 11:12 | comment | added | Turbo | @JoelDavidHamkins for complexity theory using similar terminology en.wikipedia.org/wiki/Polynomial-time_reduction. It is an open problem if they are distinct in complexity theory unlike in computability theory? The essential diff in many-one reduction in complexity theory is total computable function $f$ is replaced by polynomial function. So wondering why is it open problem in complexity theory as against in computability theory? | |
| May 7, 2016 at 11:11 | comment | added | Joel David Hamkins | Could you clarify your question? Of course there are big differences between Turing reduction and many-one reductions in computability theory, but you seem to ask not about those differences but about differences between those (different) things and some reductions (which ones?) in complexity theory? | |
| May 7, 2016 at 8:42 | history | asked | Turbo | CC BY-SA 3.0 |