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

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

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

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

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

arithmetic-circuits Shaull
источник

Конечно, эта проблема NP-сложная. (Через удовлетворяемость: у вас есть

x \lor y \equiv max {x, y}

$x\vee y \equiv \max\{x,y\}$ и

\neg x \equiv 1 - x

$\neg x \equiv 1 - x$ , с помощью которых вы можете делать AND, OR и NOT.) Итак, ваш вопрос: или нет эта проблема в NP? Решающий вопрос о том, имеет ли такая схема вход, который дает значение 1, кажется, находится в NP, поскольку, если такой вход есть, есть такой, который равен 0/1.

Нил Янг

Если мы недетерминированно выберем одно из возможных значений истинности для , где - все пары узлов, так что узел или появляется в схема, это превращается в задачу линейного программирования, которая разрешима в P. Таким образом, версия решения исходной задачи максимизации находится в NP. (Это вариант проблемы выполнимости в логике Лукасевича, поэтому вы можете обратиться к главе Ханиковой в «Руководстве по математической нечеткой логике» для получения соответствующей информации.)

\leq 2^{n}

$\le2^n$

x \leq y

$x\le y$

x, y

$x,y$

min (x, y)

$\min(x,y)$

max (x, y)

$\max(x,y)$

Эмиль Йержабек

@Shaull: позвольте мне описать это более подробно. Пусть будут узлами схемы, которые являются минимальными или максимальными вентилями (здесь ограничен размером схемы), и пусть и будут входными узлами вентиля . Для каждого выберите дополнительное ограничение или . Есть таких выборов. Когда такой выбор фиксирован, вы можете упростить схему, заменив на или

{a_{i} : i < m}

$\{a_i:i<m\}$

m

$m$

b_{i}

$b_i$

c_{i}

$c_i$

a_{i}

$a_i$

i < m

$i<m$

b_{i} \leq c_{i}

$b_i\le c_i$

c_{i} \leq b_{i}

$c_i\le b_i$

2^{m}

$2^m$

a_{i}

$a_i$

b_{i}

$b_i$

c_{i}

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

Эмиль Jeřábek

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

m

$m$

[0, 1]

$[0,1]$

\geq u

$\ge u$

\geq u

$\ge u$

Эмиль Йержабек

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

O (n)

$O(n)$

O (1)

$O(1)$

2^{O (n)}

$2^{O(n)}$

Эмиль Йержабек

Ответы:

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

Мы можем построить недетерминированное сведение задачи к линейному программированию следующим образом. Пусть будут всеми узлами которые являются минимальными или максимальными вентилями (здесь , где - размер схемы), и пусть и будут входными узлами шлюза , Для каждого выберите одно из двух дополнительных ограничений или (всего возможных вариантов). Когда такой выбор фиксирован, мы можем упростить схему, заменив каждый на или $\{a_i:i<m\}$ $C$ $m\le n$ $n$ $b_i$ $c_i$ $a_i$ $i<m$ $b_i\le c_i$ $c_i\le b_i$ $2^m$ $a_i$ $b_i$ $c_i$ в зависимости от ситуации, и результирующая схема может быть описана системой из линейных уравнений, переменные которых являются исходными входными переменными схемы, и дополнительными переменными, соответствующими узлам схемы. $n$

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

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

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

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

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

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

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

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

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

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

Питер Шор
источник

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

Шалл

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

$1-x$

Юваль Фильмус
источник

1 - x

$1-x$