Состояние наших знаний об общих арифметических схемах похоже на состояние наших знаний о булевых схемах, то есть у нас нет хороших нижних границ. С другой стороны, мы имеем экспоненциальный размер нижних границ для монотонных булевых цепей . Что мы знаем о монотонных арифметических схемах? У нас...
Является ли следующая проблема в PTIME или coNP-hard: Даны два булевых выражения и в переменных без отрицания (т. Е. Выражения полностью построены с помощью и ). Решите, есть ли , то есть имеют ли они одинаковое значение для всех назначений переменных.е1е1e_1е2е2e_2Икс1, … ,...
Разборов доказал, что соответствие монотонной функции отсутствует в мП . Но можем ли мы вычислить соответствие, используя схему полиномиального размера с несколькими отрицаниями? Существует ли P / поли схема с O(nϵ)O(nϵ)O(n^\epsilon) отрицаниями, которая вычисляет совпадение? Каков компромисс между...
P / poly - это класс задач решения, решаемых семейством булевых схем полиномиального размера. В качестве альтернативы его можно определить как машину Тьюринга за полиномиальное время, которая получает строку подсказки, которая имеет полиномиальный размер по n и основана исключительно на размере n....
Мы знаем, что проблема подсчета количества удовлетворяющих назначений в данной общей булевой формуле (CNF-SAT), заданной формуле DNF или даже заданной формуле 2SAT является проблемой # P-полной . Теперь рассмотрит CNF-SAT без отрицательного литерала (не , всегда A ). Решить задачу очень легко...
Вес |x||x||x|двоичной строки x∈{0,1}nx∈{0,1}nx\in\{0,1\}^n - количество единиц в строке. Что произойдет, если мы заинтересованы в вычислении монотонной функции на входах с несколькими из них? Мы знаем, что решить, имеет ли граф клик, сложно для монотонных цепей (см., Среди прочего, Alon Boppana,...