Исследуется задача распознавания следующего вида: для заданного многогранника требуется выяснить, достигается ли максимум линейной целевой функции в его целой точке. Устанавливается, что эта задача NP-трудна в общем случае и полиномиально разрешима в классе корневых полуметрических многоранников.
