Что известно о сложности поиска минимальных схем, которые вычисляют SAT до длины ?
Более формально: какова сложность функции, которая, учитывая качестве входных данных, выводит минимальную схему C такую, что для любой формулы φ с | φ | ≤ n , C ( φ ) = S A T ( φ ) ?
(Меня особенно интересуют нижние оценки.)
Наивный детерминистический алгоритм (вычисляет SAT грубой силой до длины , затем пробует все схемы в порядке размера, пока не найдет тот, который правильно вычисляет SAT до длины n ), занимает ≤ 2 O ( n ) времени для вычисления SAT, а затем дополнительное время O ( 2 n 2 M ) для нахождения минимальной цепи, где M - размер минимальной цепи.
Существует ли детерминированный алгоритм, который находит минимальные цепи для SAT, время работы которых составляет , где M - размер минимальной цепи? Или это подразумевает некоторый коллапс сложности?
Вот две вещи, которые, хотя и связаны с моим вопросом, определенно не соответствуют тому, о чем я спрашиваю (вот почему, мне кажется, мне было трудно это искать):
Схема задача минимизации: дана цепь (или функция F задается ее таблицей истинности, или несколько других вариантов) найти минимальную схему C ' вычислительную ту же функцию, что и C . Даже если бы минимизация схемы была легкой, это не обязательно означало бы, что вышеупомянутая задача проста, поскольку даже вычисление функции, которую мы хотим минимизировать (SAT до длины n ), считается трудным, тогда как в задаче минимизации схемы функция, которую мы хотите свести к минимуму бесплатно (это дается в качестве входных данных).
по сравнению с Р / р о л у . Мой вопрос не просто отом, какой размеримеет минимальная схема; речь идет о сложности поиска минимальной схемы, независимо от ее размера. Очевидно, что если мы можем вычислить минимальные схемы за полиномиальное время, то N P ⊆ P / p o l y (и фактически N P ⊆ P , так как тогда семейство цепей является P- равномерным), но обратное утверждение не обязательно должно быть верным. Действительно, я полагаю, чтоИммерман и Маханибыли первыми, кто построил оракула, где N но P ≠ N P - то есть, N P имеет цепи полиномиального размера, но их нельзя найти за полиномиальное время.
источник
Ответы:
источник