О сложности локального поиска в задаче о $p$-медиане

Исследуется сложность решения задачи поиска локального минимума для задачи о $p$-медиане с полиномиально проверяемыми окрестностями. Приводится достаточное условие, при выполнении которого задача поиска локального минимума с полиномиально проверяемой окрестностью является PLS-полной. Показана PSPACE-полнота задачи нахождения локального минимума с рядом полиномиально проверяемых окрестностей при фиксированной начальной точке. Установлено, что с каждой такой окрестностью алгоритм локального спуска в худшем случае требует экспоненциального числа шагов для нахождения локального минимума при любом выборе направления спуска. Предложен пример исходных данных задачи о $p$-медиане, когда алгоритм наискорейшего спуска с некоторыми полиномиально проверяемыми окрестностями требует экспоненциального числа шагов. Доказано, что если P${}\ne{}$NP, то локальный минимум относительно полиномиально проверяемой окрестности может оказаться больше глобального минимума в произвольное число раз. Установлено, что существование точной полиномиально проверяемой окрестности эквивалентно совпадению классов P и NP.