Fair enough. But identifying good subproblems of well-posed problems is a different skill from identifying good well-posed subproblems of a weird and not formalized problem. An example of the first would be to simplify the problem as much as possible without making it trivial (classic technique in algorithm analysis and design), whereas an example of the second would be defining the logical induction criterion, which creates the problems of finding a logical inductor (not sure that happened in this order, this is a part of what’s weird with problem formulation)
And I have the intuition that there are way more useful and generalizable techniques for the first case than the second case. Do you feel differently? If so, I’m really interested with techniques you have in mind for starting from a complex mess/intuitions and getting to a formal problem/setting.
I disagree with the claim that “identifying good subproblems of well-posed problems is a different skill from identifying good well-posed subproblems of a weird and not formalized problem”, at least insofar as we’re focused on problems for which current paradigms fail.
P vs NP is a good example here. How do you identify a good subproblem for P vs NP? I mean, lots of people have come up with subproblems in mathematically-straightforward ways, like the strong exponential time hypothesis or P/poly vs NP. But as far as we can tell so far, these are not very good subproblems—they are “simplifications” in name only, and whatever elements make P vs NP hard in the first place seem to be fully maintained in them. They don’t simplify the parts of the original problem which are actually hard. They’re essentially variants of the original problem, a whole cluster of problems which are probably-effectively-identical in terms of the core principles. They’re not really simplifications.
Simplifying an actually-hard part of P vs NP is very much a fuzzy conceptual problem. We have to figure out how-to-carve-up-the-problem in the right way, how to frame it so that a substantive piece can be reduced.
I suspect that your intuition that “there are way more useful and generalizable techniques for the first case than the second case” is looking at things like simplifying-P-vs-NP-to-strong-exponential-time-hypothesis, and confusing these for useful progress on the hard part of a hard problem. Something like “simplify the problem as much as possible without making it trivial” is a very useful first step, but it’s not the sort of thing which is going address the hardest part of a problem when the current paradigm fails. (After all, the current paradigm is usually what underlies our notion of “simplicity”.)
If so, I’m really interested with techniques you have in mind for starting from a complex mess/intuitions and getting to a formal problem/setting.
This deserves its own separate response.
At a high level, we can split this into two parts:
developing intuitions
translating intuitions into math
We’ve talked about the translation step a fair bit before (the conversation which led to this post). A core point of that post is that the translation from intuition to math should be faithful, and not inject any “extra assumptions” which weren’t part of the math. So, for instance, if I have an intuition that some function is monotonically increasing between 0 and 1, then my math should say “assume f(x) is monotonically increasing between 0 and 1″, not “let f(x) = x^2”; the latter would be making assumptions not justified by my intuition. (Some people also make the opposite mistake—failing to include assumptions which their intuition actually does believe. Usually this is because the intuition only feels like it’s mostly true or usually true, rather than reliable and certain; the main way to address this is to explicitly call the assumption an approximation.)
On the flip side, that implies that the intuition has to do quite a bit of work, and the linked post talked a lot less about that. How do we build these intuitions in the first place? The main way is to play around with the system/problem. Try examples, and see what they do. Try proofs, and see where they fail. Play with variations on the system/problem. Look for bottlenecks and barriers, look for approximations, look for parts of the problem-space/state-space with different behavior. Look for analogous systems in the real world, and carry over intuitions from them. Come up with hypotheses/conjectures, and test them.
Fair enough. But identifying good subproblems of well-posed problems is a different skill from identifying good well-posed subproblems of a weird and not formalized problem. An example of the first would be to simplify the problem as much as possible without making it trivial (classic technique in algorithm analysis and design), whereas an example of the second would be defining the logical induction criterion, which creates the problems of finding a logical inductor (not sure that happened in this order, this is a part of what’s weird with problem formulation)
And I have the intuition that there are way more useful and generalizable techniques for the first case than the second case. Do you feel differently? If so, I’m really interested with techniques you have in mind for starting from a complex mess/intuitions and getting to a formal problem/setting.
I disagree with the claim that “identifying good subproblems of well-posed problems is a different skill from identifying good well-posed subproblems of a weird and not formalized problem”, at least insofar as we’re focused on problems for which current paradigms fail.
P vs NP is a good example here. How do you identify a good subproblem for P vs NP? I mean, lots of people have come up with subproblems in mathematically-straightforward ways, like the strong exponential time hypothesis or P/poly vs NP. But as far as we can tell so far, these are not very good subproblems—they are “simplifications” in name only, and whatever elements make P vs NP hard in the first place seem to be fully maintained in them. They don’t simplify the parts of the original problem which are actually hard. They’re essentially variants of the original problem, a whole cluster of problems which are probably-effectively-identical in terms of the core principles. They’re not really simplifications.
Simplifying an actually-hard part of P vs NP is very much a fuzzy conceptual problem. We have to figure out how-to-carve-up-the-problem in the right way, how to frame it so that a substantive piece can be reduced.
I suspect that your intuition that “there are way more useful and generalizable techniques for the first case than the second case” is looking at things like simplifying-P-vs-NP-to-strong-exponential-time-hypothesis, and confusing these for useful progress on the hard part of a hard problem. Something like “simplify the problem as much as possible without making it trivial” is a very useful first step, but it’s not the sort of thing which is going address the hardest part of a problem when the current paradigm fails. (After all, the current paradigm is usually what underlies our notion of “simplicity”.)
This deserves its own separate response.
At a high level, we can split this into two parts:
developing intuitions
translating intuitions into math
We’ve talked about the translation step a fair bit before (the conversation which led to this post). A core point of that post is that the translation from intuition to math should be faithful, and not inject any “extra assumptions” which weren’t part of the math. So, for instance, if I have an intuition that some function is monotonically increasing between 0 and 1, then my math should say “assume f(x) is monotonically increasing between 0 and 1″, not “let f(x) = x^2”; the latter would be making assumptions not justified by my intuition. (Some people also make the opposite mistake—failing to include assumptions which their intuition actually does believe. Usually this is because the intuition only feels like it’s mostly true or usually true, rather than reliable and certain; the main way to address this is to explicitly call the assumption an approximation.)
On the flip side, that implies that the intuition has to do quite a bit of work, and the linked post talked a lot less about that. How do we build these intuitions in the first place? The main way is to play around with the system/problem. Try examples, and see what they do. Try proofs, and see where they fail. Play with variations on the system/problem. Look for bottlenecks and barriers, look for approximations, look for parts of the problem-space/state-space with different behavior. Look for analogous systems in the real world, and carry over intuitions from them. Come up with hypotheses/conjectures, and test them.