P / poly - это класс задач решения, решаемых семейством булевых схем полиномиального размера. В качестве альтернативы его можно определить как машину Тьюринга за полиномиальное время, которая получает строку подсказки, которая имеет полиномиальный размер по n и основана исключительно на размере n.
mP / poly - это класс задач решения, разрешимых семейством монотонных булевых схем полиномиального размера, но существует ли естественное альтернативное определение mP / poly в терминах машины Тьюринга за полиномиальное время?
Ответы:
Существует понятие монотонной недетерминированной и, в более общем смысле, чередующейся машины Тьюринга в статье « Монотонная сложность » Гринни и Сипсера. Поскольку полиномиальное время совпадает с переменным логарифмическим пространством, машинная характеристика унифицированного является монотонной переменной машиной логарифмического пространства Тьюринга. Предоставление такой машины с полиномиальным советом даст машинное определение .mP mP/poly
источник
На самом деле существует понятие детерминированной позитивной машины Тьюринга, которая соответствует mP / Poly. Это можно найти в статье « Положительные версии полиномиального времени » Лаутемана, Швентика и Стюарта.
источник