Timeline for Size-limited oracles
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2013 at 14:54 | comment | added | Joel David Hamkins | My view is that because the class of functions computable by your devices is not closed under composition, it is debatable whether you really have a notion of computability at all. The counterargument to this, of course, would be that even in complexity theory, we consider, say, levels of the polynomial time hierarchy, which also are not closed under composition. But the genuine notion of computability in the background there is polynomial-time computability, which of course is closed under composition. | |
| Feb 28, 2013 at 14:00 | comment | added | Micah Blake McCurdy | While I don't disagree with your comment, I don't know how much I care about the fact that my notion doesn't form a class of functions closed under composition -- maybe this cavalier-ness outs me as not really a complexity theorist at all (which I'm not). The real motivation is to focus on decomposition algorithms, and I want some way of focussing on the complexity of the decomposition of the problem, without being distracted by the complexity of the problem being decomposed; except, of course, that I realize that not all problems are so easily decomposed and I want this to show up. | |
| Feb 26, 2013 at 15:11 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |