| Die letzten 2 Beiträge |
| Karlito |
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 |
| Traidor |
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? |
|
|
