Являются ли схемы И и ИЛИ P-полными?

21

Логический элемент И & ИЛИ - это логический элемент, который получает два входа и возвращает их И и ИЛИ. Могут ли схемы, выполненные только из логического элемента И & ИЛИ без разветвления, выполнять произвольные вычисления? Точнее, сводится ли пространство журналов вычислений за полиномиальное время к цепям И & ИЛИ?

Моя мотивация для этой проблемы довольно странная. Как описано здесь , этот вопрос важен для вычислений внутри компьютерной игры Dwarf Fortress .

Итай Бар-Натан
источник
2
Такие схемы монотонны и, следовательно, далеки от P-полноты.
Дэвид Харрис
3
@ Дэвид Харрис: На первый взгляд, я тоже так думал, но эти рассуждения не верны, потому что сокращение пространства журнала может увеличить ввод с его отрицанием!
Tsuyoshi Ito
2
Можно заметить, что оценка монотонной булевой формулы завершена для при A C 0 . NC1AC0
Kaveh

Ответы:

23

Если я не неправильно понять , что вы имеете в виду и & OR ворота, это в основном компаратор ворот , который принимает два входных бита и у и производит два выходных бита х у и х у . Два выходных бита х у и х у , в основном мин ( х , у ) и максимальное ( х , у ) .ИксYИксYИксYИксYИксY(Икс,Y)(Икс,Y)

Цепи компаратора строятся путем объединения этих элементов компаратора, но не допускают разветвления, кроме двух выходов, создаваемых каждым затвором . Таким образом, мы можем нарисовать схемы компаратора, используя обозначения ниже (аналогично тому, как мы рисуем сети сортировки).

введите описание изображения здесь

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

0

Дай Ле
источник
0

(ответ недопустим, потому что он относится к отдельным элементам И, ИЛИ без ограничения разветвления)

Следующая статья посвящена теме: клеточные автоматы с большинством голосов, динамика Изинга и P-полнота

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

(...)

Проблема Monotone Circuit Value, в которой разрешены логические элементы И и ИЛИ, а логические элементы NOT - нет, по-прежнему P-полна по следующей причине: используя законы Де Моргана (...), мы можем сдвигать отрицания обратно через шлюзы до тех пор, пока они только влияет на сами входы. Таким образом, любая проблема Цепи может быть преобразована в проблему Монотонной Цепи с некоторыми отрицательными входами. Этот вид преобразования из экземпляра одной проблемы в экземпляр другой называется редукцией.

Mooncer
источник
Не могли бы вы уточнить ваш ответ? Я не смог увидеть связь между «этими системами» и цепями «И & ИЛИ», упомянутыми выше.
Дай Ле
Я прочитал газету 2 года назад. Он посвящен P-полноте и монотонным логическим схемам. Я оставляю окончательную интерпретацию читателю, потому что я не могу вспомнить детали сейчас. Это, безусловно, хорошая статья, особенно если Itai, кажется, в замешательстве. Более того: не жирный текст в моей цитате ответ - что логические схемы И / ИЛИ являются P-полными?
Mooncer
Хорошо ты прав Я, возможно, оставлю свой ответ, может быть, он будет кому-то полезен.
Mooncer
3
Хорошо известен тот факт, что проблема оценки монотонных цепей, которые состоят из вентилей И и вентилей ИЛИ, где каждый вентиль может иметь разветвление 2 , является P-полной. Проблема контура, упомянутая в оригинальном постере, накладывает ограничение на разветвление , и, следовательно, она не является P-полной.
Дай Ле
2
@vzn Схема оценки находится в P. Ссылка на факт, упомянутый Дай, - это книга Кука и Нгуена «Логические основы сложности доказательства».
Юваль Фильмус