This paper by Katta G. Murty and Santosh N. Kabadi analyzes the computational complexity of two specific problems in continuous, smooth, nonconvex nonlinear programming (NLP): checking if a given feasible solution is not a local minimum and checking if the objective function is not bounded below on the set of feasible solutions. They construct a special instance, an indefinite quadratic programming problem with integer data, and show that these problems are NP-complete. As a corollary, they also prove that the problem of checking if a given integer square matrix is not copositive is NP-complete. The authors discuss the implications of these results for the practicality of algorithms in nonconvex NLP, highlighting that verifying whether a given feasible solution is a local minimum or whether the objective function is bounded below can be computationally intensive. They provide examples, such as Fermat's Last Conjecture and the subset-sum problem, to illustrate the hardness of these problems. The paper concludes by discussing the goals for algorithms in nonconvex NLP, suggesting that a suitable goal might be to find a descent sequence converging to a KKT point, which is a feasible solution satisfying first-order necessary conditions for a local minimum.This paper by Katta G. Murty and Santosh N. Kabadi analyzes the computational complexity of two specific problems in continuous, smooth, nonconvex nonlinear programming (NLP): checking if a given feasible solution is not a local minimum and checking if the objective function is not bounded below on the set of feasible solutions. They construct a special instance, an indefinite quadratic programming problem with integer data, and show that these problems are NP-complete. As a corollary, they also prove that the problem of checking if a given integer square matrix is not copositive is NP-complete. The authors discuss the implications of these results for the practicality of algorithms in nonconvex NLP, highlighting that verifying whether a given feasible solution is a local minimum or whether the objective function is bounded below can be computationally intensive. They provide examples, such as Fermat's Last Conjecture and the subset-sum problem, to illustrate the hardness of these problems. The paper concludes by discussing the goals for algorithms in nonconvex NLP, suggesting that a suitable goal might be to find a descent sequence converging to a KKT point, which is a feasible solution satisfying first-order necessary conditions for a local minimum.