Логический элемент И & ИЛИ - это логический элемент, который получает два входа и возвращает их И и ИЛИ. Могут ли схемы, выполненные только из логического элемента И & ИЛИ без разветвления, выполнять произвольные вычисления? Точнее, сводится ли пространство журналов вычислений за полиномиальное время к цепям И & ИЛИ?
Моя мотивация для этой проблемы довольно странная. Как описано здесь , этот вопрос важен для вычислений внутри компьютерной игры Dwarf Fortress .
cc.complexity-theory
circuit-complexity
Итай Бар-Натан
источник
источник
Ответы:
Если я не неправильно понять , что вы имеете в виду и & OR ворота, это в основном компаратор ворот , который принимает два входных бита и у и производит два выходных бита х ∧ у и х ∨ у . Два выходных бита х ∧ у и х ∨ у , в основном мин ( х , у ) и максимальное ( х , у ) .Икс Y х ∧ у х ∨ у х ∧у х ∨ у ( х, у) ( х , у)
Цепи компаратора строятся путем объединения этих элементов компаратора, но не допускают разветвления, кроме двух выходов, создаваемых каждым затвором . Таким образом, мы можем нарисовать схемы компаратора, используя обозначения ниже (аналогично тому, как мы рисуем сети сортировки).
Мы можем определить проблему значения схемы компаратора (CCV) следующим образом: при наличии схемы компаратора с указанными логическими входами определите выходное значение назначенного провода. Принимая решение этой проблемы CCV при сокращении пространства журналов, мы получаем класс сложности CC , полные проблемы которого включают в себя естественные проблемы, такие как максимальное совпадение лекс-первых, устойчивый брак, устойчивый сосед.
источник
(ответ недопустим, потому что он относится к отдельным элементам И, ИЛИ без ограничения разветвления)
Следующая статья посвящена теме: клеточные автоматы с большинством голосов, динамика Изинга и P-полнота
источник