Problem in BPP, aber nicht in RP oder Co-RP bekannt

Antworten:

21

Verschob meinen Kommentar hier nach Sureshs Bitte.

Ein Beispiel für ein natürliches Problem, für das wir nur Algorithmen kennen, die auf beiden Seiten Fehler erfordern, ist das Folgende: Entscheiden Sie bei drei gegebenen algebraischen Kreisen, ob genau zwei davon identisch sind. Dies beruht auf der Tatsache, dass die Entscheidung, ob zwei algebraische Kreise identisch sind, im Co-RP erfolgt.

Referenz: siehe die Post Wie viele Seiten zu Ihrem Fehler? (2. Dezember 2008) zu genau derselben Frage in Lance Fortnows Blog und den Kommentaren unter seinem Beitrag für eine Diskussion über die Natürlichkeit des Problems.

Alessandro Cosentino
quelle
20

Ein wohl natürlicheres Problem - nicht speziell für das Auffinden eines Problems entwickelt, das in , und auch nicht so eng mit einem Problem verwandt ist, von dem bekannt ist, dass es in c o R P vorkommt - wird durch Aufgabe 2.6 von [1] geliefert: Hat die von A erzeugte Gruppe bei gegebener Primzahl p , Ganzzahlen N und d und einer Liste A von invertierbaren Matrizen d × d über F p einen Quotienten der Ordnung N ?BPPRPcoRPcoRPpNdEINd×dFpEINNohne abelsche normale Untergruppen? In [1] wird gezeigt, dass dieses Problem in .BPP

Während die Frage nach Quotienten ohne abelsche normale Untergruppen exzentrisch erscheinen mag, ist die Klasse von Gruppen ohne abelsche normale Untergruppen (manchmal als Semisimple bezeichnet) vom Standpunkt der Strukturtheorie von Gruppen eigentlich ziemlich natürlich. Siehe [2] und Referenzen darin.

[1] L. Babai, R. Beals, A. Seress. Polynom-Zeit-Theorie von Matrixgruppen . STOC 2009.

[2] L. Babai, P. Codenotti, Y. Qiao. Polynomialzeit-Isomorphismustest für Gruppen ohne abelsche normale Untergruppen . Zu erscheinen, ICALP 2012.

Joshua Grochow
quelle