Каково эквивалентное определение mP / poly в терминах машины Тьюринга?

13

P / poly - это класс задач решения, решаемых семейством булевых схем полиномиального размера. В качестве альтернативы его можно определить как машину Тьюринга за полиномиальное время, которая получает строку подсказки, которая имеет полиномиальный размер по n и основана исключительно на размере n.

mP / poly - это класс задач решения, разрешимых семейством монотонных булевых схем полиномиального размера, но существует ли естественное альтернативное определение mP / poly в терминах машины Тьюринга за полиномиальное время?

Джесси Стерн
источник
3
AFAIK, у нас нет понятия машин Тьюринга, соответствующих монотонным цепям. Так что ответ - нет.
Каве
Я подумал, что это может быть так. Любые заметные дискуссии, в Интернете или в газетах, по вопросу о выражении классов, разрешимых с помощью семейств схем ограниченного размера, которые являются монотонными или имеют ограниченное число отрицаний, с точки зрения ограниченной по времени машины Тьюринга? Являются ли их конкретные барьеры для определения таких классов, или люди просто не беспокоятся?
Джесси Стерн

Ответы:

15

Существует понятие монотонной недетерминированной и, в более общем смысле, чередующейся машины Тьюринга в статье « Монотонная сложность » Гринни и Сипсера. Поскольку полиномиальное время совпадает с переменным логарифмическим пространством, машинная характеристика унифицированного является монотонной переменной машиной логарифмического пространства Тьюринга. Предоставление такой машины с полиномиальным советом даст машинное определение .mPmP/poly

Ян Йоханнсен
источник