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?
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