I think canonical high-degree polynomial problem is high-dimensional search. We usually don’t implement exact grid search because we can deploy Monte Carlo or gradient descent. I wonder if there is any hard lower bounds on approximation hardness for polynomial time problems.
I think canonical high-degree polynomial problem is high-dimensional search. We usually don’t implement exact grid search because we can deploy Monte Carlo or gradient descent. I wonder if there is any hard lower bounds on approximation hardness for polynomial time problems.