Простое доказательство того, что проблема удовлетворенности цепи-NP-Hard

Question

$ newcommand { np} { mathsf {np}} newcommand { cc} { textrm {circuit-sat}} $ У меня трудно понять доказательство $ np $ -hardness для $ cc $ in CLRS.

$ cc = { langle c rangle: c text {это удовлетворительная комбинаторная логическая схема} } $

Лемма: Проблема $ cc $-$ mathsf {np} $-тяжело.

Может ли кто-нибудь предоставить простые для понимания доказательство?

Answer 1

(Очень) упрощенная версия заключается в том, что они преобразуют любой алгоритм проверки $ a $ для языка $ l in text {np} $ в схему.

То, что они в конечном итоге, - это схема $ C $, которая, учитывая (бинарную) строку $ x $, удовлетворена (т. Е. Сертификат $ y $ такой, что $ a (x, y) = 1 $).

Они делают это, кодируя работу алгоритма, воплощенного какой -то машиной Тьюринга (то есть функция перехода) в качестве цепи $ M $. Общая схема $ C $ является серией конкатенаций $ M $, где входные значения для каждой итерации $ M $ представляют собой бинарное кодирование состояния TM, воплощающего $ A $.

Поскольку каждый бит этого (включая количество шагов $ a $ принимает) полиномиально ограничен размером $ x $, схема может быть построена в многочленное время.

Таким образом, они дают в целом, это полиномиальный способ построения схемы, имитирующей $ a $, установленную по шагам, которая удовлетворяется тогда и только в том случае, если мы сможем найти какой -то сертификат, который $ x in l $. Затем, если бы мы могли решить в полиномиальное время, если $ C $ удовлетворит, мы бы знали, что есть какой -то сертификат, который доказывает $ x in l $, следовательно, решив $ l $ в многочтное время.