Том 12, серия 2, номер 2, 2005 г., Стр. 44-71
УДК 519.85
Ю. А. Кочетов, М. Г. Пащенко, А. В. Плясунов
О сложности локального поиска в задаче $p$-медиане
Аннотация:
Исследуется сложность решения задачи поиска локального минимума для задачи о$p$ -медиане с полиномиально проверяемыми окрестностями. Приводится достаточное условие, при выполнении которого задача поиска локального минимума с полиномиально проверяемой окрестностью является PLS-полной. Показана PSPACE-полнота задачи нахождения локального минимума с рядом полиномиально проверяемых окрестностей при фиксированной начальной точке. Установлено, что с каждой такой окрестностью алгоритм локального спуска в худшем случае требует экспоненциального числа шагов для нахождения локального минимума при любом выборе направления спуска. Предложен пример исходных данных задачи о$p$ -медиане, когда алгоритм наискорейшего спуска с некоторыми полиномиально проверяемыми окрестностями требует экспоненциального числа шагов. Доказано, что если P${}\ne{}$ NP, то локальный минимум относительно полиномиально проверяемой окрестности может оказаться больше глобального минимума в произвольное число раз. Установлено, что существование точной полиномиально проверяемой окрестности эквивалентно совпадению классов P и NP.
Кочетов Ю. А. 1
Пащенко М. Г. 1
Плясунов А. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: apljas@math.nsc.ru, jkochet@math.nsc.ru, pashch@math.nsc.ru
Статья поступила 28 октября 2004 г.
Исправленный вариант — 20 октября 2005 г.
