Computational complexity of norm-maximization (Q757258)

The paper is concerned with the computational complexity of the decision problem that arises in attempting to maximize a quasi-convex function \(\phi\) over a convex polytope P in n-space that is presented as the intersection of a finite number m of closed half spaces. This problem is NP-hard (for variable n) when \(\phi\) is the pth power of the classical p- norm. For this problem the question arises whether there exists \(y\in P\) such that \(\phi\) (y)\(\geq \beta\), where \(\beta\) is an integer. The present reexamination of the problem establishes NP-hardness for a wide class of functions, and for the p-norm it proves the NP-hardness of maximization over n-dimensional parallelotopes that are centered at the origin or have a vertex there. Some main conclusions are as follows: The problems of \(\{\)-1,1\(\}\)-maximization and \(\{\) 0,1\(\}\)-maximizatin of a positive definite quadratic norm are NP-complete. For maximizing the Euclidean norm over a rectangular parallelotope in \(R^ n\) there is an algorithm that uses only n inner-product computations and n-1 comparisons. The expositions assumes some familiarity with the classes P and NP, and with the rudiments of the theory of NP-completeness.