В 1980-х годах Разборов, как известно, показал, что существуют явные монотонные булевы функции (такие как функция CLIQUE), которые требуют экспоненциально большого количества вентилей AND и OR для вычисления. Однако базис {AND, OR} над булевой областью {0,1} является лишь одним примером интересного набора элементов, который не может быть универсальным. Это приводит к моему вопросу:
Существует ли какой-либо другой набор вентилей, интересно отличающийся от монотонных вентилей, для которых известны экспоненциальные нижние границы размера схемы (без глубины или других ограничений на схему)? Если нет, то существует ли какой-либо другой набор элементов, который является вероятным кандидатом для таких нижних границ - границ, которые не обязательно требуют прорыва через барьер Natural Proofs, как это было в результате монотонных схем Разборова?
Если такой набор затворов существует, то, конечно, он будет выше k-арного алфавита для k≥3. Причина в том, что в двоичном алфавите
(1) монотонные ворота ({И, ИЛИ}),
(2) линейные ворота ({NOT, XOR}) и
(3) универсальные ворота ({И, ИЛИ, НЕ})
в основном исчерпывают интересные возможности, как следует из теоремы Поста о классификации. (Обратите внимание, что я предполагаю, что константы --- 0 и 1 в двоичном случае --- всегда доступны бесплатно.) С линейными вентилями каждая булева функция f: {0,1} n → {0,1} это вычислимый вообще вычислим по схеме линейного размера; с универсальным набором, конечно, мы столкнулись с естественными доказательствами и другими ужасающими барьерами.
С другой стороны, если мы рассмотрим наборы ворот для алфавита из 3 или 4 символов (например), то откроется более широкий набор возможностей - и, по крайней мере, насколько мне известно, эти возможности никогда не были полностью намечены с точки зрения теории сложности (поправьте меня, если я ошибаюсь). Я знаю, что возможные множества ворот широко изучаются под названием «клоны» в универсальной алгебре; Хотелось бы, чтобы я был более знаком с этой литературой, чтобы я знал, что, если что-нибудь, результаты из этой области значат для сложности схемы.
В любом случае, не может быть и речи о том, что есть другие нижние границы драматического контура, готовые к испытанию, если мы просто расширим класс наборов гейтов по конечным алфавитам, которые мы готовы рассмотреть. Если я не прав, скажите, пожалуйста, почему!
источник
Ответы:
(Удалено из комментариев, как предложил Суреш. Обратите внимание, что некоторые ошибки в комментарии исправлены здесь.)
Спасибо Скотту за отличный вопрос.
Скотт, кажется, предполагает, что причиной сложности нижних границ может быть ограниченный язык операций в булевом случае. Счетный аргумент Шеннона, который показывает, что большинство цепей должно быть большим, основан на разрыве между счетной выразительной силой и бесчисленным количеством цепей. Этот пробел исчезает, когда в алфавите есть как минимум 3 символа.
Для размера алфавита 2 (логический случай) решетка клонов счетно бесконечна и называется решеткой Поста .
Решетка Поста также поясняет, почему для булева случая есть только несколько интересных базисов операций.
Для размера алфавита 3 или более решетка клонов неисчислима. Кроме того, решетка не удовлетворяет какой-либо нетривиальной идентичности решетки, поэтому представляется невозможным дать полное описание решетки. Для размера алфавита 4 или более решетка клонов фактически содержит каждую конечную решетку в качестве подрешетки. Таким образом, существует бесконечно много, возможно, интересных основ операций, которые нужно учитывать, когда в алфавите 3 или более символов.
Скотт спросил далее: остается ли решетка клонов несчетной, если предположить, что константы доступны бесплатно?
Ответ таков: посмотрите, например,
хотя, видимо, это было опубликовано ранее:
Хорошее конкретное утверждение от:
В заключение, я не знаю какой-либо работы по использованию небулевых клонов для нижних границ схемы. Это, кажется, стоит исследовать более подробно. Учитывая относительно мало что известно о решетке клонов, могут быть интересные основы операций, ожидающих своего открытия.
Дополнительные связи между теорией клонов и информатикой, вероятно, также будут представлять большой интерес для математиков, работающих в универсальной алгебре. Предыдущий пример такого рода взаимодействия появился, когда Питер Дживонс показал, что алгебры могут быть связаны с языками ограничений таким способом, который позволяет преобразовывать результаты отслеживаемости в свойства алгебры. Андрей Булатов использовал это, чтобы доказать дихотомию для CSP с размером домена 3. С другой стороны, в результате применения компьютерных наук наблюдается оживление интереса к теории ручного сравнения. Интересно, что следует из связи между теорией клонов и сложностью небулевой схемы.
источник
Это убрано из комментариев, как предложил Суреш.
Редактировать 2. Основным препятствием является то, что у нас нет никаких методов для доказательства нелинейных нижних границ, даже для линейных ворот, насколько я знаю (для линейных нижних границ можно использовать исключение ворот, что очень маловероятно, чтобы -линейные границы). Хотя, похоже, некоторые методы из линейной алгебры действительно должны быть полезны. Поэтому подходить к кандидатам приятно, но в любом случае нужны новые методы.
источник
источник