(This may not be a research level question per se. I can delete this question if the community thinks this way too)

I am trying to understand how to reason about hardness of optimization problems when the input contains closed form functions. In my problem, I have buyer revenue curves as I put in closed form and I have to find an optimal output curve that maximizes revenue (the exact details are not important). On one hand, I can use the oft used tricks of discretizing and getting $(1+\epsilon)$-approximation FPTAS, I am not sure how to reason about NP hardness of these type of problems. One approach would be to show the hardness of the discrete version of the problem. While this works great since it is a special case of the continuous version but does not give the whole picture since the continuous function may also be differentiable (or double differentiable) which may have a huge impact on the answer.

Is there a general framework or hardness reduction techniques that work on closed form functions as input?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.