Jaka jest równoważna definicja mP / poli w odniesieniu do maszyny Turinga?

13

P / poly to klasa problemów decyzyjnych rozwiązanych przez rodzinę obwodów boolowskich wielkości wielomianowych. Alternatywnie można go zdefiniować jako wielomianową maszynę Turinga, która otrzymuje ciąg porady, który jest wielomianem wielkości w n, i który opiera się wyłącznie na rozmiarze n.

mP / poli to klasa problemów decyzyjnych rozwiązanych przez rodzinę monotonicznych obwodów boolowskich o wielomianowym rozmiarze, ale czy istnieje naturalna alternatywna definicja mP / poli w odniesieniu do maszyny Turinga o wielomianowym czasie?

cc.complexity-theory complexity-classes circuit-complexity polynomial-time monotone Jesse Stern
źródło
3
AFAIK, nie mamy pojęcia maszyn Turinga odpowiadających obwodom monotonicznym. Więc odpowiedź brzmi nie.
Kaveh
Uznałem, że może tak być. Jakieś znaczące dyskusje, zarówno w Internecie, jak i na papierze, na temat wyrażania klas możliwych do rozwiązania przez rodziny obwodów o ograniczonych rozmiarach, które są monotonne lub mają ograniczoną liczbę negacji, jeśli chodzi o ograniczoną czasowo maszynę Turinga? Czy są ich specyficzne bariery w definiowaniu takich klas, czy też ludzie po prostu nie przejmują się?
Jesse Stern

Odpowiedzi:

15

mPmP/poly

Jan Johannsen
źródło
7

W rzeczywistości istnieje pojęcie deterministycznej pozytywnej maszyny Turinga, która pasuje do mP / Poly. Można go znaleźć w artykule Pozytywne wersje czasu wielomianowego autorstwa Lautemana, Schwenticka i Stewarta

Thomas S.
źródło