Контекстно-зависимая грамматика для SAT?

16

Классическим результатом Куроды является то, что класс сложности NSPACE [ ]N (также известный как NLIN-SPACE) является именно классом CSL контекстно-зависимых языков . Задача выполнимости SAT находится в NSPACE [ ], так как предположение линейного размера для решения может быть проверено не более чем с линейной величиной накладных расходов для учета. Это означает, что SAT должен иметь контекстно-зависимую грамматику (CSG).N

Кто-нибудь пытался предоставить CSG для SAT?

Я понимаю, что многие вопросы, связанные с CSL, неразрешимы (например, решение, генерирует ли данный CSG пустой язык). Даже при наличии CSG для SAT все равно придется преодолеть препятствие, заключающееся в том, что решение о членстве на языке, указанном в CSG, в целом является PSPACE-полным. Но может случиться так, что проблема членства для CSG, которая определяет SAT, находится в NP, из-за некоторой особой структуры языка. Перефразируя, обращаясь к комментарию MCH: Но может быть так, что проблема членства для CSG, которая определяет SAT, может быть показана в NP из-за некоторой специальной структуры грамматики, а не потому, что мы уже знаем, что она должна быть в NP.

  • S.-Y. Курода, Классы языков и линейно-ограниченные автоматы , Информация и управление 7 (2) 207–223, 1964. doi: 10.1016 / S0019-9958 (64) 90120-2

Разъяснение:

Предполагаемый фокус здесь - это особенность грамматики для SAT, которая позволяет распознавать ее на машине NTIME [poly ( )], а не на границе NSPACE [ n ] DTIME [ 2 O ( n ) ].NN2О(N)

Доказательство теоремы 3 в работе Ландвебера 1963 года строит CSG из линейно ограниченного автомата. (Курода предоставил обратное, построив линейно-ограниченный автомат для любой CSG.) Однако процедура Ландвебера, по-видимому, не дает грамматику для SAT, которая имеет особую форму: все распознаватели NSPACE [ ] обрабатываются одинаковым образом. Другими словами, неясно, почему в SAT CSG должна быть проблема членства в NP, а не PSPACE-полная. Я надеялся на более явную конструкцию, которая использует NP-ность SAT каким-то существенным образом.N

Возможно, лучше, более точный вопрос:

  1. существует линейно ограниченный автомат, который распознает SAT,
  2. из которого можно извлечь CSG,
  3. так что язык, определенный CSG, находится в NP из-за некоторой особенности грамматики (а не потому, что мы уже знаем, что это в NP)?

За прошедшие пять десятилетий наверняка кто-то пытался сделать это! Поскольку я не могу найти что-либо опубликованное по этим направлениям, мне было бы интересно понять, почему этот подход не работает, или указатель на работу, который я пропустил.

  • Питер С. Ландвебер, Три теоремы о грамматиках структуры фраз типа 1 , Информация и управление 6 (2) 131–136, 1963. doi: 10.1016 / S0019-9958 (63) 90169-4
Андраш Саламон
источник
5
Я не понимаю Разве вы не можете просто следовать доказательству и создать CSG для SAT? Это неконструктивно? Также о последнем предложении, «это может быть так , что проблема членства в CSG , которая определяет SAT в НП», он находится в НП , поскольку проблема членства только СБ, который находится в НП.
MCH
1
@ МЧ: Спасибо за ваш комментарий, я надеюсь, что редактирование прояснит вопрос.
Андрас Саламон
это звучит как другой способ выразить это, может быть так: существуют CSL / CSG, которые распознаются во время NP (в отличие от PSPACE в общем случае) на основе преобразования SAT. Что особенного в их «структуре», которая позволяет это? преобразование SAT в CSL / CSG может дать «подсказку», но не обязательно. дать более общие критерии. другими словами, учитывая произвольный CSL / CSG, существуют ли какие-либо критерии, которые указывают, что его распознавание действительно в NP?
vzn

Ответы:

9

Несмотря на то, что непосредственно не создается контекстно-зависимая грамматика для SAT, следующая статья может пролить некоторый свет.

Раунды WC, Сложность распознавания в языках среднего уровня , Теория коммутации и автоматов, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5

Статья Раунда дает однонаправленный недетерминированный стековый автомат (1-NSA), распознающий SAT, а затем показывает, что проблема принадлежности 1-NSA (и его надлежащего надмножества, индексированная грамматика Aho) в общем случае в NP. Другими словами, SAT как CSL / linear-bounded-автоматы особенные в том смысле, что они используют свою память только как стек.

kinaba
источник
4
Спасибо, именно то, что я искал! Раунды показывают, что SAT является языком одностороннего стека, индексированным языком и языком преобразователей дерева, давая три разных теоретико-языковых причины, почему он такой особенный.
Андрас Саламон
так что может быть «достаточно», но не сразу понятно, необходимы ли эти условия (для распознавания CSL / CSG в NP). так что мне кажется, что ваш общий вопрос мало изучен. CSLs / CSGs, кажется, не имеют большого количества исследований позади них.
ВЗН
дальше думал об этом. Его проблема, как правило, в форме «является признание языка в большем классе Y на самом деле в меньшем классе языка X». для Y = CFG и X = RLs (обычный язык) проблема неразрешима, см. например , определяет ли этот cfg регулярный язык . следовательно, Y = CSL и X = NP, по-видимому, в целом также неразрешимы.
ВЗН