---

Geschrieben von Traidor am 22.04.2013 um 16:06:

  Beweis(-Idee) für NP=RP*?

Meine Frage:
Hallo zusammen,

ich bin auf der Suche nach einem Beweis oder einer Beweisidee für NP=RP*.

Meine Ideen:
Ich kann mir ungefähr vorstellen, dass man das über DTM und PTM beweisen kann bzw. über die Definition der Komplexitätsklassen. Aber eine wirkliche Idee habe ich nicht.

Kann mir jemand auf die Sprünge helfen?

---

Geschrieben von Karlito am 23.04.2013 um 14:01:

 

Hallo,

die typische herangehensweise ist doch, dass man sich ein NP-vollständiges Problem und ein Problem aus RP-vollständiges Problem sucht und versucht nachzuweisen, dass diese gleich schwer sind. Dazu wird eine Abbildung des NP-Problems in das RP-Problem gesucht (Reduktion).

Das wäre der Ansatz, den ich wählen würde. Einen anderen kenne ich ehrlich gesagt auch gerade nicht.

VG,

Karlito