Your overall picture sounds pretty similar to mine. A few differences.
I don’t think the literal version of (2) is plausible. For example, consider an obfuscated circuit.
The reason that’s OK is that finding the de-obfuscation is just as easy as finding the obfuscated circuit, so if gradient descent can do one it can do the other. So I’m really interested in some modified version of (2), call it (2′). This is roughly like adding an advice string as input to P, with the requirement that the advice string is no harder to learn than M itself (though this isn’t exactly right).
I mostly care about (1) because the difficulty of (1) seems like the main reason to think that (2′) is impossible. Conversely, if we understood why (1) was always possible it would likely give some hints for how to do (2). And generally working on an easier warm-up is often good.
I think that if (1) is false in general, we should be able to find some example of it. So that’s a fairly high priority for me, given that this is a crucial question for the feasibility or character of the worst-case approach.
That said, I’m also still worried about the leap from (1) to (2′), and as mentioned in my other comment I’m very interested in finding a way to solve the harder problem in the case of primality testing.
Your overall picture sounds pretty similar to mine. A few differences.
I don’t think the literal version of (2) is plausible. For example, consider an obfuscated circuit.
The reason that’s OK is that finding the de-obfuscation is just as easy as finding the obfuscated circuit, so if gradient descent can do one it can do the other. So I’m really interested in some modified version of (2), call it (2′). This is roughly like adding an advice string as input to P, with the requirement that the advice string is no harder to learn than M itself (though this isn’t exactly right).
I mostly care about (1) because the difficulty of (1) seems like the main reason to think that (2′) is impossible. Conversely, if we understood why (1) was always possible it would likely give some hints for how to do (2). And generally working on an easier warm-up is often good.
I think that if (1) is false in general, we should be able to find some example of it. So that’s a fairly high priority for me, given that this is a crucial question for the feasibility or character of the worst-case approach.
That said, I’m also still worried about the leap from (1) to (2′), and as mentioned in my other comment I’m very interested in finding a way to solve the harder problem in the case of primality testing.