Я могу частично ответить на ваш вопрос: подсчет локальных оптимумов задачи поиска с полным PLS действительно может быть # P-сложным.
Во-первых, как указывает Йошио, существует проблема поиска в PLS, чья связанная проблема подсчета является # P-полной. (Однако мы не знаем, является ли P 1 PLS-полным.) Пусть P 2 - некоторая PLS-полная задача. Затем определите P ′, который на входе ( x , i ) для i ∈ { 1 , 2 } запрашивает локальный оптимум для входа x относительно P i . Эта проблема наследует PLS членство P 1 , P 2п1п1п2п'( х , я )i ∈ { 1 , 2 }Икспяп1, P2, наследует PLS-полноту , а для задачи подсчета наследует # P-полноту P 1 .п2п1
Точно так же можно построить (искусственную) PLS-полную задачу, для которой она является NP-полной, чтобы решить, существует ли более одного локального оптимума. Как и в предыдущем аргументе, один «скоба» а вместе PLS-полная задача , как и прежде, с проблемой PLS , P 2 , который, на входе булевой формулы ψ , имеет более одного локального оптимум , связанные тогда и только тогда ψ выполним.п1п2ψψ
Подобные конструкции несколько неудовлетворительны, потому что мы пытаемся построить задачу поиска которая имеет два свойства твердости, но область Q «разбивается» на две части, каждая из которых может иметь только одно из двух свойств. Ниже я покажу, как, учитывая задачу поиска P 1 в PLS, для которой связана проблема подсчета # P-complete, и учитывая задачу P 2 , завершающую PLS , можно определить задачу Q PLS, которая так же сложна, как и подсчет P 1 и поиск P 2 способом «экземпляр за экземпляром».QQп1п2Qп1п2
А именно, мы покажем таким образом, что решение проблемы подсчета для P 1 на входе x эффективно сводится к решению проблемы подсчета для Q на входе x , а задача поиска для P 2 на входе x сводится к задаче поиска для Q на вход х .Qп1ИксQИксп2ИксQИкс
Для простоты изложения мы предполагаем, что таковы, что на любом входе x длины n пространство решения-кандидата, связанное с x, находится над цепочками битов y длины n c для некоторого c (но с различными структурами окрестности для P 1 , P 2 ). Пусть F i ( x , y ) - фитнес-функция, связанная с P i .п1, P2ИксNИксYNссп1, P2Fя( х , у)пя
На входе пространство поиска для 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( у1, у2, z, Б )Yя{ 0 , 1 }NсZ∈ { 0 , 1 }Nс+ 1b ∈ { 0 , 1 }, В качестве функции пригодности для Q определимF( х , ( у1, у2, z, Б ) )Q
если b = 1 , F( х , ( у1, у2, z, б ) ) : = F1( х , у1) + F2( х , у2)б = 1
если b = 0 .F( х , ( у1, у2, z, б ) ) : = | | Y1| | + | | Z| | + F2( х , у2)б = 0
(Это вес Хэмминга выше.)
Для структуры окрестности мы связываем каждый кортеж ( x , ( y 1 , y 2 , z , 1 ) ) (с b = 1 ) со всеми кортежами ( x , ( ( y ′ ) 1 , ( y ′ ) 2 , z ′ , 1 ) ) такой, чтоQ( х , ( у1, у2, z, 1 ) )б = 1( х , ( ( у')1, ( у')2, z', 1 ) )
(A) соединяется с ( x , ( y ' ) i ) согласно P i для i = 1 , 2 И(х , уя)( х ,( у')я)пяя = 1 , 2
(В) отличаются не более 1 координат.Z, z'
Для кортежей с мы связываем ( x , ( y 1 , y 2 , z , 0 ) ) со всеми кортежами ( x , ( ( y ′ ) 1 , ( y ′ ) 2 , z ′ , 0 ) ), такими этоб = 0( х , ( у1, у2,z, 0 ) )( х , ( ( у')1, ( у')2, z', 0 ) )
(A ') соединен с ( x , ( y ' ) 2 ) согласно P 2 , И( х , у2)( х , ( у')2)п2
(B ') отличаются не более чем на 1 координату, как и y 1 , ( y ′ ) 1 .Z, z'Y1, ( у')1
(Обратите внимание, что кортежи с связаны с кортежами с b = 1. )б = 0б = 1
Это определение . При необходимости окрестности имеют полиномиальный размер, поэтому Q находится в PLS. QQ
Утверждение : локальные оптимумы для длины входного x в соответствии с Q - это в точности следующие два непересекающихся множества:NИксQ
(1) все кортежи , где ( x , y i ) - локальный оптимум P i для каждого из i = 1 , 2 (и z произвольно, и б = 1 ); и,( х , ( у1, у2, z, 1 ) )( х , уя)пяя = 1 , 2Zб = 1
(2) все кортежи , где ( x , y 2 ) - локальный оптимум P 2 , и где z , y 1 оба равны all-1s, и б = 0 .(x,1nc,y2,1n,0))(x,y2)P2z,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
Рассмотрим проблему максимального соответствия в двудольных графах. Семейство возможных решений состоит из всех соответствий, а локальный поиск выполняется путем поиска путей расширения. Проблема относится к PLS, так как путь расширения может быть найден за полиномиальное время, если текущее соответствие не является максимальным, а максимальность может быть проверена за полиномиальное время. Любой локальный оптимум является максимальным соответствием (т. Е. Глобальным оптимумом). Однако # P-трудно вычислить количество максимальных совпадений в двудольном графе.
Поскольку локальный оптимум может быть найден за полиномиальное время, проблема вряд ли будет PLS-полной. Итак, я боюсь, что это не намеченный ответ (ваш вопрос ограничен PLS-полными проблемами). Тем не менее, я должен отметить, что подсчет количества локальных оптимумов может быть трудным, даже если один локальный оптимум может быть найден эффективно.
источник