Что известно о сложности поиска минимальных каналов для SAT?

23

Что известно о сложности поиска минимальных схем, которые вычисляют SAT до длины ? n

Более формально: какова сложность функции, которая, учитывая качестве входных данных, выводит минимальную схему C такую, что для любой формулы φ с | φ | n , C ( φ ) = S A T ( φ ) ?1nCφ|φ|nC(φ)=SAT(φ)

(Меня особенно интересуют нижние оценки.)

Наивный детерминистический алгоритм (вычисляет SAT грубой силой до длины , затем пробует все схемы в порядке размера, пока не найдет тот, который правильно вычисляет SAT до длины n ), занимает 2 O ( n ) времени для вычисления SAT, а затем дополнительное время O ( 2 n 2 M ) для нахождения минимальной цепи, где M - размер минимальной цепи. nn2O(n)O(2n2M)M

Существует ли детерминированный алгоритм, который находит минимальные цепи для SAT, время работы которых составляет , где M - размер минимальной цепи? Или это подразумевает некоторый коллапс сложности?o(2n2M)M


Вот две вещи, которые, хотя и связаны с моим вопросом, определенно не соответствуют тому, о чем я спрашиваю (вот почему, мне кажется, мне было трудно это искать):

  • Схема задача минимизации: дана цепь (или функция F задается ее таблицей истинности, или несколько других вариантов) найти минимальную схему C ' вычислительную ту же функцию, что и C . Даже если бы минимизация схемы была легкой, это не обязательно означало бы, что вышеупомянутая задача проста, поскольку даже вычисление функции, которую мы хотим минимизировать (SAT до длины n ), считается трудным, тогда как в задаче минимизации схемы функция, которую мы хотите свести к минимуму бесплатно (это дается в качестве входных данных).CfCCn

  • по сравнению с Р / р о л у . Мой вопрос не просто отом, какой размеримеет минимальная схема; речь идет о сложности поиска минимальной схемы, независимо от ее размера. Очевидно, что если мы можем вычислить минимальные схемы за полиномиальное время, то N P P / p o l y (и фактически N P P , так как тогда семейство цепей является P- равномерным), но обратное утверждение не обязательно должно быть верным. Действительно, я полагаю, чтоИммерман и Маханибыли первыми, кто построил оракула, где NNPP/polyNPP/polyNPPP но P N P - то есть, N P имеет цепи полиномиального размера, но их нельзя найти за полиномиальное время.NPP/polyPNPNP

Джошуа Грохов
источник
Вы хотите безусловные нижние границы? (Конечно, сложность времени меньше ограничена сложностью схемы SAT, но мы не знаем по существу ничего конкретного о последнем.)
Райан Уильямс,
@Ryan: Как это часто бывает, безоговорочно было бы неплохо, но на это, вероятно, слишком много надежды. Я добавил второй вопрос о сложности с точки зрения размера вывода (= размер минимальной схемы), чтобы прояснить это в качестве примера.
Джошуа Грохов
3
Ах, теперь я понимаю. Это очень хороший вопрос. Может быть возможно улучшить наивную границу, используя идеи из алгоритмов для изучения схем SAT, Bshouty et al. Если вы уже нашли схему для SAT до некоторого размера, возможно, вы можете загрузить ее и использовать для более эффективного поиска схемы большего размера.
Райан Уильямс

Ответы:

12

T(n)=poly(T(n))2Ω(n)

ST(T(n))2o(M)T(n)=2no(1)

Боаз Барак
источник