P / poly ist die Klasse von Entscheidungsproblemen, die durch eine Familie von Booleschen Schaltungen polynomialer Größe lösbar sind. Es kann alternativ als eine Polynom-Zeit-Turing-Maschine definiert werden, die eine Hinweiszeichenfolge empfängt, die in n polynomisch ist und die ausschließlich auf der Größe von n basiert.
mP / poly ist die Klasse von Entscheidungsproblemen, die von einer Familie von monotonen Booleschen Schaltkreisen polynomialer Größe gelöst werden können. Gibt es jedoch eine natürliche alternative Definition von mP / poly in Bezug auf eine polynomiale Zeit-Turing-Maschine?
cc.complexity-theory
complexity-classes
circuit-complexity
polynomial-time
monotone
Jesse Stern
quelle
quelle
Antworten:
Die monotone Komplexität von Grigni und Sipser beschreibt eine monotone nicht deterministische und allgemein alternierende Turing-Maschine . Da die Polynomzeit mit dem alternierenden logarithmischen Raum identisch ist, ist eine Maschinencharakterisierung mit einheitlichem die monotone alternierende logarithmische Maschine. Die Bereitstellung einer solchen Maschine mit Polynom Rat wird dann eine Maschinendefinition von dem , m P / p o l y .m P m P / p o l y
quelle
Es gibt tatsächlich einen Begriff einer deterministischen positiven Turing-Maschine, der mit mP / Poly übereinstimmt. Es ist in dem Artikel Positive Versions of Polynomial Time von Lauteman, Schwentick und Stewart zu finden
quelle