# Can ALL Optimization Problems be Classified as "P" vs "NP"?

In the context of Computer Science and Optimization, I have heard that different problems can be classified using the "P vs NP" framework. Essentially, there is a hierarchy of problems based on the inherent complexity of the problem itself. For example, a problem like "multiplying numbers" is considered as "P" and is considered fundamentally easier to solve than a problem like "solving a sudoku" which is "NP".

In most Statistical and Machine Learning Models, there is usually an optimization problem "nested" within the model that is required to solve. For example:

• Regression Models: In a standard regression model, we try to find the value of the "beta coefficients" that either minimize the error between the (candidate) model's prediction of the response variable and true values of the response variable (Ordinary Least Squares - OLS), or we try to find the "beta coefficients" such that probability of reproducing the observed response values is maximized (Maximum Likelihood Estimation - MLE). For simple regression models, there exists "exact solutions" to the OLS and MLE optimization problems and we can calculate these "beta coefficients" analytically - but in more sophisticated regression models such as Logistic Regression or Regularized Regression (e.g. LASSO, RIDGE), the corresponding optimization problem is usually solved using some approximate and iterative algorithm such as the "Newton-Raphson" Method.

• Decision Trees: A Decision Tree (e.g. CART) is formed by "splitting" variables into smaller subsets (i.e. "nodes") such that "purity" increases in each subsequent subset; "purity" is often measured through some sort of "Information Gain" that is based on measures such as "Gini Index" or "Entropy". Thus, Decision Trees can be interpreted as an optimization problem where "Information Gain" has to be optimized. I have heard that since Decision Trees often have different variable types (e.g. continuous and categorial), searching for the optimal variable splits that optimize "Information Gain" is a Mixed Integer Optimization Problem having an enormous Combinatorial Search Space. For the interest of creating a decent Decision Tree in a reasonable amount of time, "Information Gain" is optimized using a "Greedy Search Algorithm," and as a result, the final Decision Tree (i.e. the answer to this Mixed Integer Optimization Problem) is almost certainly unlikely to be the optimal Decision Tree (as there is very high probability that a better Decision Tree likely exists in this large Combinatorial Search Space, but finding this Decision Tree would take too much time):

• Neural Networks: Successful Neural Networks are largely attributed to the effectiveness of Optimization Algorithms (e.g. Stochastic Gradient Descent) to optimize (i.e. determine the "neuron weights") notoriously complicated, high dimensional and non-convex Loss Functions:

My Question: Is it possible to categorize the optimization problems corresponding to Statistical and Machine Learning Models such as Regression Models, Decision Trees, and Neural Networks as "P" vs "NP"?

I am aware that categorizing these problems wont really have any effect on solving them, but I have the following guess: When provided with a candidate solution to any of these optimization problems (e.g. Regression beta coefficients, a particular Decision Tree, Neural Network Weights), we have no real way of checking whether this candidate solution is indeed the optimal solution (unlike a sudoku, in which even for an enormous "n x n" sudoku, we can instantly check if a candidate solution violates the rules or not). Thus, my guess is that many of these above optimization problems are likely either NP-Complete or NP-Hard.

Is this correct?

Note: I have often heard of Machine Learning Optimization Problems being described as "Ill-Posed Problems", implying that they are inherently more difficult than "Well-Posed Problems" (Why is pattern recognition often defined as an ill-posed problem?). This is due to factors such as solutions to these optimization problems "may not exist" and "may not be unique". However, I am not sure if "Ill-Posed Problems" automatically leave the "N" and "NP" complexity classes.

• First comment: the precise definitions of NP and NP-whatever are fairly picky, and in particular there is some difference between "decidable" in polynomial time (the computer science version of NP-whatever, which came first) and "solvable" in polynomial time (the optimization version, which came later). Second comment: NP-Hard is not the hardest problem level out there. Being in NP (including NP-Hard) requires that (somewhat loosely speaking) answers can be verified in polynomial time. There could conceivably be problems where even that is not true.
– prubin
Feb 7 at 1:54
• @ prubin: thank you for your reply! i was interested in this idea in a very general sense. For instance - if you take the problem of optimizing the loss function of a neural network. Could we assign some "designation" to this general problem (e.g. P, NP, NP-Hard, etc.)? Feb 7 at 5:22
• Note that, as your diagram correctly shows, P is a subset of NP. So, if a problem is in P, then it is also in NP. Also note that we don't know whether there exist problems that are in NP but not in P.
– Stef
Feb 7 at 11:50
• No, it's not typical for traditional analyses of neural-networks to discuss complexity-classes.
– Nat
Feb 7 at 12:26
• Sorry, I don't know enough about loss functions used to train neural nets to say whether the problems fall into P, NP or some other category.
– prubin
Feb 7 at 16:49

No. There are optimization problems that are strictly in EXPTIME or other complexity higher complexity. Picking the optimal move in a Go game on a $$n\times n$$ grid is EXPTIME in $$n$$. MaxSAT on QBF (quantified boolean formulas) is in PSPACE. Those examples are of harder complexity classes then NP and because of that the P vs NP distinction is irrelevant for them.