Характеристика одноразовых формул по полному двоичному базису

15

Фон

Формула однократного чтения для набора элементов (также называемая базисом) - это формула, в которой каждая входная переменная появляется один раз. Формулы однократного чтения обычно изучаются на основе де Моргана (которая имеет 2-битные логические элементы И и ИЛИ, и 1-битный вентиль НЕ) и полной двоичной базе данных (которая имеет все 2-битные логические элементы).

Так, например, AND из 2 битов может быть записано в виде формулы для однократного чтения на любой основе, но четность в 2 бита не может быть записана в виде формулы для однократного чтения на основе De Morgan.

Множество всех функций, которые можно записать в виде формулы для однократного чтения на основе де Моргана, имеет комбинаторную характеристику. См., Например, комбинаторную характеристику одноразовых формул М. Карчмера, Н. Линиала, И. Ньюмана, М. Сакса, А. Вигдерсона.

Вопрос

Существует ли альтернативная характеристика набора функций, которая может быть вычислена по формуле однократного чтения по полному двоичному базису?

Более простой вопрос (добавлено в v2)

Хотя я все еще заинтересован в ответе на исходный вопрос, так как я не получил никаких ответов, я подумал, что задам более простой вопрос: какие методы нижней границы работают с формулами по всей двоичной основе? (Кроме тех, которые я перечисляю ниже.)

Обратите внимание, что сейчас я пытаюсь опустить нижнюю границу размера формулы (= количество листьев). Для одноразовых формул у нас есть формула size = количество входов. Таким образом, если вы можете доказать, что функция нуждается в формуле размера, строго превышающей n, то это также означает, что она не может быть представлена ​​в виде формулы для однократного чтения.

Мне известны следующие приемы (вместе со справочником по каждому приему из Сложности булевых функций: достижения и границы Стасиса Юкны ):

  • Метод Нечипорука для универсальных функций (раздел 6.2): ​​показывает нижнюю границу размера для определенной функции. Это не поможет вам найти нижние границы для конкретной функции, которая вас может заинтересовать.n2−o(1)
  • Ω(n2/log⁡n)
cc.complexity-theory circuit-complexity lower-bounds formulas Робин Котари
источник
Вы смотрели в BDD, бинарные диаграммы решений ? разве они не достаточно близки по сложности? но, не видел спецификацию на Subj.
vzn

Ответы:

-2

есть также метод, называемый нижней границей Крапченко, «который может быть немного больше, чем метод Нечипорукса». см. John E Savage, Модели вычислений, раздел 9.4.2. (который описан сразу после метода Нечипорука в разделе 9.4.1)

ВЗН
источник
2
Спасибо за ссылку, но метод Крапченко работает только на основе Де Моргана (называемой «стандартной основой» в книге Сэвиджа). Мой вопрос о полной двоичной основе.
Робин Котари
если метод Нечипорукса работает над полной двоичной базой, а метод показан на основе методики Де Моргана / стандартной в книге Savages, то почему Крапченкос не работает над обеими? но согласился, что у Сэвиджа нет примера Крапченко / полного бинарного базиса.
vzn
1
Полный двоичный базис является надмножеством базиса Де Моргана. Любые нижние границы, которые работают против полной двоичной основы, также работают против основы Де Моргана.
Робин Котари
хорошо, хорошо, что исключает метод Крапченко, работающий на полной двоичной основе? Я подозреваю, что метод Нечипорука был, вероятно, впервые применен к базису де Моргана, а затем расширен до полной основы, верно? что исключает метод Крапченко?
vzn