This is a cool fact I hadn’t been aware of. An alternative sketch (it might be nonsense, not being careful):
If P = NP then P = co-NP. The problem of “given x, say yes if x is the argmax of f” is co-NP, because you can polynomially verify “no” answers: a witness is y such that f(y) > f(x). So this is in P, i.e. we can polynomially answer “is this the argmax”. Since we can polynomially verify this, the map from polytime TMs for some f, to argmax, is in FNP. (<- This step is the one I’m slightly unconfident about but seems right.) So this map is in P since FNP = P (presumably).
I think this is spiritually quite similar to your proof, except that the binary search thing isn’t necessary?
This is a cool fact I hadn’t been aware of. An alternative sketch (it might be nonsense, not being careful):
If P = NP then P = co-NP. The problem of “given x, say yes if x is the argmax of f” is co-NP, because you can polynomially verify “no” answers: a witness is y such that f(y) > f(x). So this is in P, i.e. we can polynomially answer “is this the argmax”. Since we can polynomially verify this, the map from polytime TMs for some f, to argmax, is in FNP. (<- This step is the one I’m slightly unconfident about but seems right.) So this map is in P since FNP = P (presumably).
I think this is spiritually quite similar to your proof, except that the binary search thing isn’t necessary?