Насколько сложно посчитать количество локальных оптимумов для проблемы в PLS?

11

Для полиномиальной задачи локального поиска мы знаем, что должно существовать хотя бы одно решение (локальный оптимум). Тем не менее, может существовать гораздо больше решений, насколько сложно сосчитать количество решений для PLS-полной задачи? Меня особенно интересует проблема решения: есть ли у этого экземпляра полной проблемы PLS два или более решений?

Зависит ли сложность от того, какую PLS-полную задачу мы выберем? Если так, то меня особенно интересует взвешенный 2SAT (как определено в [SY91] и [Rou10]). Я знаю, что подсчет количества удовлетворяющих решений для 2SAT является # P-полным, но на первый взгляд кажется, что локальные оптимумы взвешенного 2SAT и решения для 2SAT не имеют ничего общего.

Я также знаю, что для PPAD, двоюродного брата PLS, [CS02] показывает, что подсчет числа равновесий по Нэшу является # P-сложным. Это говорит о том, что подобные проблемы PLS, такие как подсчет количества равновесий с чистой стратегией в играх с перегрузками, также будут сложными.

Рекомендации

[CS02] Конитцер В. и Сандхольм Т. (2002). Сложность результатов о равновесиях Нэша. IJCAI-03 . CS / 0205074 .

[Rou10] T. Roughgarden. (2010). Вычислительные равновесия: перспектива вычислительной сложности. Экономическая теория , 42: 193-236.

[SY91] А.А. Шеффер и М. Яннакакис. (1991). Простые проблемы локального поиска, которые трудно решить. SIAM Journal по вычислительной технике , 20 (1): 56-87.

Артем Казнатчеев
источник

Ответы:

7

Я могу частично ответить на ваш вопрос: подсчет локальных оптимумов задачи поиска с полным PLS действительно может быть # P-сложным.

Во-первых, как указывает Йошио, существует проблема поиска в PLS, чья связанная проблема подсчета является # P-полной. (Однако мы не знаем, является ли P 1 PLS-полным.) Пусть P 2 - некоторая PLS-полная задача. Затем определите P ′, который на входе ( x , i ) для i { 1 , 2 } запрашивает локальный оптимум для входа x относительно P i . Эта проблема наследует PLS членство P 1 , P 2P1P1P2P(x,i)i{1,2}xPiP1,P2, наследует PLS-полноту , а для задачи подсчета наследует # P-полноту P 1 .P2P1

Точно так же можно построить (искусственную) PLS-полную задачу, для которой она является NP-полной, чтобы решить, существует ли более одного локального оптимума. Как и в предыдущем аргументе, один «скоба» а вместе PLS-полная задача , как и прежде, с проблемой PLS , P 2 , который, на входе булевой формулы ψ , имеет более одного локального оптимум , связанные тогда и только тогда ψ выполним.P1P2ψψ

Подобные конструкции несколько неудовлетворительны, потому что мы пытаемся построить задачу поиска которая имеет два свойства твердости, но область Q «разбивается» на две части, каждая из которых может иметь только одно из двух свойств. Ниже я покажу, как, учитывая задачу поиска P 1 в PLS, для которой связана проблема подсчета # P-complete, и учитывая задачу P 2 , завершающую PLS , можно определить задачу Q PLS, которая так же сложна, как и подсчет P 1 и поиск P 2 способом «экземпляр за экземпляром».QQP1P2QP1P2

А именно, мы покажем таким образом, что решение проблемы подсчета для P 1 на входе x эффективно сводится к решению проблемы подсчета для Q на входе x , а задача поиска для P 2 на входе x сводится к задаче поиска для Q на вход х .QP1xQxP2xQx

Для простоты изложения мы предполагаем, что таковы, что на любом входе x длины n пространство решения-кандидата, связанное с x, находится над цепочками битов y длины n c для некоторого c (но с различными структурами окрестности для P 1 , P 2 ). Пусть F i ( x , y ) - фитнес-функция, связанная с P i .P1,P2xnxynccP1,P2Fi(x,y)Pi

На входе пространство поиска для Q находится над кортежами ( y 1 , y 2 , z , b ), где каждый y i находится в { 0 , 1 } n c , z { 0 , 1 } n c + 1 и b { 0 , 1 }x{0,1}nQ(y1,y2,z,b)yi{0,1}ncz{0,1}nc+1b{0,1}, В качестве функции пригодности для Q определимF(x,(y1,y2,z,b))Q

если b = 1 , F(x,(y1,y2,z,b)):=F1(x,y1)+F2(x,y2)b=1

если b = 0 .F(x,(y1,y2,z,b)):=||y1||+||z||+F2(x,y2)b=0

(Это вес Хэмминга выше.)

Для структуры окрестности мы связываем каждый кортеж ( x , ( y 1 , y 2 , z , 1 ) )b = 1 ) со всеми кортежами ( x , ( ( y ) 1 , ( y ) 2 , z , 1 ) ) такой, чтоQ(Икс,(Y1,Y2,Z,1))бзнак равно1(x,((y)1,(y)2,z,1))

(A) соединяется с ( x , ( y ' ) i ) согласно P i для i = 1 , 2 И(x,yi)(x,(y)i)Pii=1,2

(В) отличаются не более 1 координат.z,z

Для кортежей с мы связываем ( x , ( y 1 , y 2 , z , 0 ) ) со всеми кортежами ( x , ( ( y ) 1 , ( y ) 2 , z , 0 ) ), такими этоb=0(Икс,(Y1,Y2,Z,0))(Икс,((Y')1,(Y')2,Z',0))

(A ') соединен с ( x , ( y ' ) 2 ) согласно P 2 , И(Икс,Y2)(Икс,(Y')2)п2

(B ') отличаются не более чем на 1 координату, как и y 1 , ( y ) 1 .Z,Z'Y1,(Y')1

(Обратите внимание, что кортежи с связаны с кортежами с b = 1. )бзнак равно0бзнак равно1

Это определение . При необходимости окрестности имеют полиномиальный размер, поэтому Q находится в PLS. QQ

Утверждение : локальные оптимумы для длины входного x в соответствии с Q - это в точности следующие два непересекающихся множества:NИксQ

(1) все кортежи , где ( x , y i ) - локальный оптимум P i для каждого из i = 1 , 2z произвольно, и б = 1 ); и,(Икс,(Y1,Y2,Z,1))(Икс,Yя)пяязнак равно1,2Zбзнак равно1

(2) все кортежи , где ( x , y 2 ) - локальный оптимум P 2 , и где z , y 1 оба равны all-1s, и б = 0 .(Икс,1Nс,Y2,1N,0))(Икс,Y2)п2z,y1b=0

Если вы согласны, то PLS-твердость является непосредственным, так как любой локальный оптимум ( х , ( у 1 , у 2 , г , б ) ) из Q для ввода х дает локальный оптимум ( х , у 2 ) в Р 2 (для того же входа x ), а P 2 - PLS-жесткий.Q(x,(y1,y2,z,b))Qx(x,y2)P2xP2

Кроме того, из нашего утверждения следует, что число локальных оптимумов для x при Q равно ( 2 n c + 1 N 1 ( x ) + 1 ) N 2 ( x ) , где N i ( x ) равно число локальных оптимумов для x при P i . Теперь N 2 ( x ) находится в диапазоне [ 1N(x)xQ(2nc+1N1(x)+1)N2(x)Ni(x)xPiN2(x) , поэтому мы имеем[1,2nc]

mod 2 n c + 1 = ( 2 n c + 1 N 1 ( x ) + 1 ) N 2 ( x ) mod 2 n c + 1 = N ( x ) mod 2 n c + 1 .N2(x)=N2(x)2nc+1=(2nc+1N1(x)+1)N2(x)2nc+1=N(x)2nc+1

Таким образом, мы можем получить учетом N ( x ) . Тогда мы также можем получить N 1 ( x ) с помощью простой алгебры: N 1 ( x ) = ( N ( x )N2(x)N(x)N1(x). ПосколькуN1(x)является # P-полным для вычисления, то же самое относится и кN(x). Таким образом, # P-complete для подсчета локальных оптимумов дляQ(и подсчет дляP1сводится к подсчетуQдля того же экземпляра). N1(x)=(N(x)N2(x)1)/2nc+1N1(x)N(x)QP1Q


Я не знаю, как дать такое уменьшение для сочетания PLS-твердости с NP-твердостью для определения уникальности локальных оптимумов способом «экземпляр за экземпляром».

Что касается того, дает ли каждая проблема поиска с полным PLS проблему подсчета с полным # P, я также не знаю этого. Это кажется связанно с вопросом о том, для каждой NP-полной задача Решения L и каждые полиномиального по верификатору для L , ассоциированная задача свидетеля подсчета является # Р-полной. # П-полнота сохраняется во всех конкретных случаях, которые рассматривали люди, и при некоторых достаточно мягких условиях, но в целом является открытой. Смотрите это обсуждение .V(x,y)L

Для конкретной, более естественной проблемы известной как PLS-полная, можно установить # P-полноту для подсчета локальных оптимумов, задав PLS-сокращение от Matching до Q, которое имеет некоторые специальные свойства, подходящие для подсчета. Возможно существующих методов достаточно; Я не пытался выяснить.QQ

Энди Друкер
источник
Чем ты, Энди! Это очень полезно. Мне придется прочитать его еще пару раз, чтобы убедиться, что я следую всему.
Артем Казнатчеев
7

Рассмотрим проблему максимального соответствия в двудольных графах. Семейство возможных решений состоит из всех соответствий, а локальный поиск выполняется путем поиска путей расширения. Проблема относится к PLS, так как путь расширения может быть найден за полиномиальное время, если текущее соответствие не является максимальным, а максимальность может быть проверена за полиномиальное время. Любой локальный оптимум является максимальным соответствием (т. Е. Глобальным оптимумом). Однако # P-трудно вычислить количество максимальных совпадений в двудольном графе.

Поскольку локальный оптимум может быть найден за полиномиальное время, проблема вряд ли будет PLS-полной. Итак, я боюсь, что это не намеченный ответ (ваш вопрос ограничен PLS-полными проблемами). Тем не менее, я должен отметить, что подсчет количества локальных оптимумов может быть трудным, даже если один локальный оптимум может быть найден эффективно.

Ёсио Окамото
источник
Благодаря! Это хороший общий момент, чтобы узнать о # P-твердости в целом (и почему я упомянул 2SAT). Я буду держать этот вопрос открытым в надежде получить некоторые ответы на проблемы, полные PLS, а также сделаю больший акцент на различении одного решения, существующего от двух или более существующих решений (это тот случай, который меня на самом деле больше всего интересует).
Артем Казнатчеев
1
Поскольку уникальность максимального соответствия может быть эффективно проверена, мой ответ не является удовлетворительным для вопроса, который вас больше всего интересует. Спасибо.
Ёсио Окамото