Какова минимальная необходимая глубина снижения NP-твердости SAT?

14

Как все знают, SAT завершен для сравнению с многозначным сокращением за полиномиальное время. Это все еще полные сокращения wrt много-один.NPAC0

Мои вопросы: какова минимальная необходимая глубина для сокращений? Более формально,

Что наименьшее такое, что SAT - это -hard wrt много-один сокращений?dNPACd0

Мне кажется, что должно быть достаточно? Кто-нибудь знает ссылку?AC20

cc.complexity-theory reference-request np-hardness circuit-complexity reductions Кава
источник
3
На первый взгляд кажется, что на ваш вопрос следует ответить «Маниндра Агравал, Эрик Аллендер, Стивен Рудич, Сокращение сложности цепей: теорема об изоморфизме и теорема о разрыве», JCSS 57: 127-143, 1999 ». Они говорят: «Мы доказываем, что все наборы, завершенные для NP при сокращениях AC0, завершаются при сокращениях, которые вычисляются по двум цепям AC0 глубины». Но я могу что-то упустить.
Робин Котари
@ Робин, спасибо, я проверю редукции сложности схем : теорема об изоморфизме и теорема о разрыве .
Каве
@ Робин, я думаю, что он положительно отвечает на мой вопрос: « Теорема 10. (Теорема разрыва). Пусть C - любой правильный класс сложности. Наборы, сложные для C при неоднородных сокращениях AC0, трудны для C при неоднородных сокращениях NC0 ». и « Следствие 4. для любого собственного класса сложности C, каждый набор в комплекте для C под сокращением NC0 завершен под сокращением вычислит глубины два AC0 схем и обратимая глубиной три AC0 цепи. » , где собственно означает " закрыт под DLogTime-равномерных сокращений NC1 ». Вы хотите опубликовать это как ответ, чтобы я мог принять это?
Каве
Хорошо, я сделаю репост
Робин Котари

Ответы:

8

Повторно разместив мой комментарий:

На первый взгляд кажется, что на ваш вопрос следует ответить «Маниндра Агравал, Эрик Аллендер, Стивен Рудич, Сокращение сложности цепей: теорема об изоморфизме и теорема о разрыве» , JCSS 57: 127-143, 1999 ». Они говорят: «Мы доказываем, что все наборы, завершенные для NP при сокращениях AC0, завершаются при сокращениях, которые вычисляются по двум цепям AC0 глубины». Но я могу что-то упустить.

Робин Котари
источник