Timeline for Is there such a notion as "effectively computable reductions" or would this be not useful
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27, 2020 at 16:03 | vote | accept | StefanH | ||
| Feb 25, 2020 at 21:39 | answer | added | Caleb Stanford | timeline score: 6 | |
| Feb 25, 2020 at 20:43 | comment | added | StefanH | Yes, maybe it is more about how to interpret the exists-quantifier more constructively. Your remark about "iterative doubling" does not really help, googling does not reveal anything related, and otherwise if I get you right you mean "allocating" space/"SAT variables" as necessary in an "iterative doubling" way, okay than it might be something like 2(p(n)+1) to much space allocated, but with this procedure I think you would capture all subexponential running times too, not just the polynomial ones, but maybe I have understood you simply wrong on that... | |
| Feb 25, 2020 at 18:26 | comment | added | D.W.♦ | Nice question! I think one can construct an effective Cook reduction, by iterative doubling. Does that help? (Nitpick: I suspect this is about constructiveness not about computability: there are functions that we know are computable but where we don't know how to constructively provide an algorithm for them.) | |
| Feb 25, 2020 at 18:07 | history | asked | StefanH | CC BY-SA 4.0 |