Арифметические схемы с ,

12

Рассмотрим схему, которая принимает в качестве входных чисел числа из [0,1] и имеет логические элементы, состоящие из функций max(x,y) , min(x,y) , 1x и x+y2 . Выход схемы также является числом в [0,1] .

Кто-нибудь знает, изучалась ли эта модель или тесно связанная модель?

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

Примечание: мое исследование этой модели проводится с помощью взвешенной временной логики, поэтому любые модели, которые относятся к последней, также могут пригодиться.

Shaull
источник
5
Конечно, эта проблема NP-сложная. (Через удовлетворяемость: у вас есть ИксYМаксимум{Икс,Y} и ¬Икс1-Икс , с помощью которых вы можете делать AND, OR и NOT.) Итак, ваш вопрос: или нет эта проблема в NP? Решающий вопрос о том, имеет ли такая схема вход, который дает значение 1, кажется, находится в NP, поскольку, если такой вход есть, есть такой, который равен 0/1.
Нил Янг
3
Если мы недетерминированно выберем одно из возможных значений истинности для , где - все пары узлов, так что узел или появляется в схема, это превращается в задачу линейного программирования, которая разрешима в P. Таким образом, версия решения исходной задачи максимизации находится в NP. (Это вариант проблемы выполнимости в логике Лукасевича, поэтому вы можете обратиться к главе Ханиковой в «Руководстве по математической нечеткой логике» для получения соответствующей информации.) x y x , y min ( x , y ) max ( x , y )2nxyx,ymin(x,y)max(x,y)
Эмиль Йержабек
5
@Shaull: позвольте мне описать это более подробно. Пусть будут узлами схемы, которые являются минимальными или максимальными вентилями (здесь ограничен размером схемы), и пусть и будут входными узлами вентиля . Для каждого выберите дополнительное ограничение или . Есть таких выборов. Когда такой выбор фиксирован, вы можете упростить схему, заменив на илиm b i c i a i i < m b ic i c ib i 2 m a i b i c i{aя:я<м}мбясяaii<mbicicibi2maibiciв зависимости от обстоятельств, поэтому он превращается в систему линейных уравнений, переменные являются исходные переменные задачи, а также дополнительные переменные , соответствующие ...
Эмиль Jeřábek
4
... узлы в цепи. Включите неравенств, утверждающих, что дополнительные ограничения выполнены, неравенства, ограничивающие исходные переменные значением , и неравенство, указывающее, что выходной узел имеет значение . Тогда это линейная программа, зависящая от выбора дополнительных ограничений, и схема достигает значения если существует выбор ограничений, так что соответствующая линейная программа имеет решение. [ 0 , 1 ] u um[0,1]uu
Эмиль Йержабек
5
Также отметим, что оптимальное значение линейной программы достигается в вершине многогранника. Это означает, что знаменатель оптимального решения может быть выражен как определитель матрицы измерения , записи которой являются целыми числами постоянного размера, и в каждой строке есть только ненулевых записей, и как таковой он ограничен . О(N)2 O ( n )О(1)2О(N)
Эмиль Йержабек

Ответы:

12

Задача выполнимости для этих цепей (т. Е. Учитывая схему и , решает, есть ли вход такой, что ) находится в NP, и, следовательно, NP-завершается Комментарий Нила Янга и ответ Питера Шора.u [ 0 , 1 ] x C ( x ) uCu[0,1]xC(x)u

Мы можем построить недетерминированное сведение задачи к линейному программированию следующим образом. Пусть будут всеми узлами которые являются минимальными или максимальными вентилями (здесь , где - размер схемы), и пусть и будут входными узлами шлюза , Для каждого выберите одно из двух дополнительных ограничений или (всего возможных вариантов). Когда такой выбор фиксирован, мы можем упростить схему, заменив каждый на илиC m n n b i c i a i i < m b ic i c ib i 2 m a i b i c i n{ai:i<m}СмNNбясяaяя<мбясясябя2мaябясяв зависимости от ситуации, и результирующая схема может быть описана системой из линейных уравнений, переменные которых являются исходными входными переменными схемы, и дополнительными переменными, соответствующими узлам схемы.N

Мы также включили неравенств, утверждающих, что дополнительные ограничения выполнены, неравенства, ограничивающие исходные входные переменные в , и неравенство, утверждающее, что выходной узел имеет значение . Тогда это линейная программа размера зависимости от выбора дополнительных ограничений, и схема достигает значения если существует выбор ограничений, так что соответствующая линейная программа имеет решение. Поскольку линейное программирование в P, это показывает, что проблема в NP.м[0,1]UО(N)U

Также отметим, что оптимальное значение линейной программы достигается в вершине многогранника. Это означает, что знаменатель оптимального решения может быть выражен как определитель квадратной матрицы размерности , записи которой являются целыми числами постоянного размера, и в каждой строке есть только ненулевых записей, и как таковой оно ограничено .О(N)O(1)2O(n)

Подобные редукции часто полезны, чтобы дать верхние оценки сложности выполнимости в пропозициональных нечетких логиках (таких как логика Лукасевича) и связанных с ними системах. (На самом деле исходная проблема - это второстепенный вариант выполнимости в Лукасевиче, который будет соответствовать схемам с вместо ) Обзор связанных результатов можно найти в главе X Справочника по математической нечеткой логике, Vol. II.( х + у ) / 2min(1,x+y)(x+y)/2

Эмиль Йержабек
источник
4

Эта проблема NP-сложная.

Вы можете получить 3-SAT с воротами min ( x , y ), max ( x, y ) и 1− x .

Мы хотим свести проблему 3-SAT к схеме, для которой вы можете получить 1, если все переменные выполнимы, и в противном случае вы можете достичь только чего-то строго меньше 1.

Мы можем заставить все переменные быть 0 или 1, взяв минимум много выражений, и сделать так, чтобы эти выражения включали max ( x , 1− x ).

Теперь для каждого предложения в задаче 3-SAT xyz положим выражение max ( x , y , z ) в минимум.

Я не знаю, каково оптимальное значение для неудовлетворительной задачи 3-SAT, но оно будет строго меньше 1.

Питер Шор
источник
2
Да, NP-твердость является «легким направлением», как указано в комментарии выше. На самом деле, если вы не используете средний вентиль, а просто min и max, легко показать, что максимальное значение равно 1, если соответствующая логическая схема выполнима, и 1/2 в противном случае (просто подключив 1/2 ко всем переменные). Во всяком случае, проблема была решена в комментариях выше.
Шалл
1

Не совсем то, что вы просили, но контекст, в котором появляются подобные схемы.

1-Икс

Юваль Фильмус
источник
3
1-Икс