Классы семантической и синтаксической сложности

35

В своей книге «Вычислительная сложность» Пападимитриу пишет:

RP в некотором смысле новый и необычный вид сложности класса. Ни одна полиномиально ограниченная недетерминированная машина Тьюринга не может быть основой для определения языка в RP. Чтобы машина N могла определить язык в RP , она должна обладать замечательным свойством, которое на всех входах она либо отклоняет единогласно , либо принимает большинством . Большинство недетерминированных машин ведут себя по-другому, по крайней мере, на некоторых входах ... Нет простого способа определить, всегда ли машина останавливается с сертифицированным выходом. Мы неофициально называем такие классы семантическими классами , в отличие от таких синтаксических классов , как P и NP.где мы можем немедленно определить поверхностной проверкой, действительно ли соответствующим образом стандартизированная машина определяет язык в классе.

Несколько страниц спустя он указывает, что:

язык L находится в классе PP, если существует недетерминированная полиномиально ограниченная машина Тьюринга N, такая, что для всех входов x, если только более половины вычислений N на входе x в конечном итоге принимают. Мы говорим, что N решает L большинством .xL

Вопрос 1: Почему Пападимитриу приходит к выводу, что PP является синтаксическим классом, а его определение лишь немного отличается от определения в RP ?

Вопрос 2: Является ли «семантическое» для класса сложности эквивалентно НЕ иметь полных проблем, или отсутствие полных проблем воспринимается как свойство, которым мы обладаем семантическими классами GUESS?

Изменить: См. Связанную тему Все ли классы сложности имеют характеристики языка листьев?

М.С. Дусти
источник
2
недавний доклад Ануджа Давара из INI: о синтаксических и семантических классах сложности
Kaveh
@Kaveh: Большое спасибо! Я посмотрю на это.
MS Dousti

Ответы:

31

RP включает в себя обещание, что либо 0 путей принимают, либо принимают более половины, независимо от того, что ввод. Для ПП такого обещания нет. Если более половины пути принимают, то , в противном случае, . (PP можно определить так, чтобы критерии составляли и соответственно.)х L 1 / 2 < 1 / 2xLxL1/2<1/2

Или, другими словами, если я дам вам вероятностную TM, утверждающую, что это машина PP, решающая какой-то язык, вы можете быть уверены, что она решит какой-то язык. Ясно, что язык, который он решает, является следующим: Попробуйте ввести . Посмотрите, принимает ли более 1/2 пути (или более 1/2 случайных строк, которые его принимают). Если да, . Если нет, . Итак, мы определили язык, используя эту ТМ.x L x LxxLxL

С другой стороны, если я дам вам вероятностную TM, утверждающую, что это RP-машина, решающая какой-то язык, вы даже не можете быть уверены, что она решит какой-либо язык. Проблема в том, что когда вы наблюдаете принятие только нескольких путей, вы не знаете, находится ли в или нет. Так что, если я дам вам RP-машину, вы просто должны поверить мне на слово. Действительно, проверка того, определяет ли этот компьютер язык, невычислима.лxL

Что касается вашего второго вопроса, то для синтаксических классов обычно существует очевидная полная проблема, которая выглядит так: «Для заданной машины M решите, принимает ли она время T на входе x». Если у вас есть недетерминированный компьютер, эта проблема является NP-полной, если это PP-машина, то она PP-полная и т. Д. Очевидная полная проблема для семантических классов, как я уже говорил, неразрешима. Таким образом, мы не получаем полную проблему бесплатно для семантических классов. Но у семантического класса может быть полная проблема. Например, если P = BPP (как принято считать), то BPP имеет синтаксическую характеристику.

РЕДАКТИРОВАТЬ : Поскольку есть некоторые дискуссии о том, как определить семантические и синтаксические классы, я хотел бы отметить, что Пападимитриу дает определение в своей книге, говоря о листовых языках. (См. Мой вопрос о листовых языках для некоторых ссылок.)

Он говорит, что синтаксические классы - это те, для которых существует некоторый язык, который определяет класс с использованием техники листового языка. Семантические классы - это те, для которых все такие характеристики требуют проблем с обещаниями. Это строгое определение, но оно работает только для тех языков, которые имеют листовые языковые характеристики.

Робин Котари
источник
3
Ну, я бы не потратил впустую последние 20 минут на написание своего ответа, если бы только что перезагрузил страницу ... :) Я оставлю это на всякий случай, если это также будет полезно.
Райан Уильямс
Да, я ненавижу, когда это происходит. Хотя иногда я получаю уведомление «новые ответы опубликованы» в середине написания ответа.
Робин Котари
6
@Robin: Вам не пришлось прибегать к недоказанному, но широко распространенному утверждению «P = BPP» для примера интенционально семантического класса, который оказывается синтаксическим: IP = PSPACE. (А теперь и QIP тоже.)
Джошуа Грохов
3
@ Джошуа: Вы правы, IP = PSPACE работает.
Робин Котари
1
@ Джошуа: Спасибо за упоминание результата IP = PSPACE. Я никогда не смотрел на это с этой точки зрения!
MS Dousti
28

Ответ на ваш первый вопрос заключается в том, что в определении нет «обещания» для машины, как с . Каждый случайный многочленный множитель определяет некоторый язык : на каждом входе либо машина принимает случайных путей вычислений на соответствующих входах, либо нет. Первый случай означает, что в языке, второй случай означает, что его нет.Р Р Р Р > 1 / 2 хPPRP PP>1/2x

Следовательно, как и в случае с и , мы можем дать рекурсивный список всех машин , просто перечислив все рандомизированные машины с многопоточностью. В отличие от этого, с существуют рандомизированные машины, которые принимают (например) ровно одну из случайных строк на входе, и в этом случае машина не удовлетворяет ни одному из условий для : она не принимает на своей случайные строки, и он не отклоняет все строки. Следовательно, эта рандомизированная машина не является машиной в том смысле, что она имеет «неопределенное» поведение на некотором подмножестве входов. Это приводит к определениюН Р Р Р Р Р Р Р > 1 / 2 Р Р Р г о м я сек е - Р РPNPPPRPRP>1/2RPPromiseRP, где вы рассматриваете «проблемы обещания», которые допускают произвольное поведение на некоторых строках. См. Зоопарк Сложности для больше.

Это приводит к вопросу 2. Проблема с понятием «семантический класс» заключается в том, что он зависит от машин, которые вы используете для определения класса, и, следовательно, его очень трудно правильно определить. (Я не уверен, что когда-либо было дано полностью удовлетворительное определение.) Быть «семантическим классом» примерно эквивалентно указанному выше свойству: не каждая машина (в естественном списке машин) будет удовлетворять необходимым условиям принятия / отклонения для вашего класса, и, следовательно, «сложно» получить список машин, которые принимают именно языки в вашем классе. Но если , то есть некоторый легко вычислимый список некоторыхП = Б П ПP=BPPмашины, которые принимают в точности языки вашего класса, а именно список машин, вычисляемых за полиномиальное время. Следовательно, может показаться, что если окажется, что , мы превратили семантический класс в синтаксический.P=BPP

Если бы это действительно было так, что просто не существует легко вычислимого списка машин (любого разумного типа), которые бы принимали именно ваш класс, тогда да, я не думаю, что у вашего класса может быть полный язык. Но это кажется очень трудно правильно оформить, не говоря уже о том, чтобы доказать.

Райан Уильямс
источник
Привет Райан. Считаете ли вы, что можно определить синтаксический подход, предполагая что-то вроде тезиса Черч-Тьюринга?
Каве
1
Я отредактировал свой ответ сейчас, чтобы ответить на вопрос, как определить синтаксичность.
Робин Котари