Alle NP-Probleme reduzieren sich auf NP-vollständige Probleme: Wie können NP-Probleme nicht NP-vollständig sein?

2 answers
  • Wenn A auf B reduziert wird, reduziert sich B auf A?

    Nein. Für ein wirklich durchdachtes Beispiel ist jedes mögliche berechenbare Problem A auf das Halting-Problem reduzierbar: Als Eingabe übergeben Sie einfach den Algorithmus, der das Problem A löst, aber mit einem while(true) am Ende nach entweder dem richtigen oder dem falschen Fall. Wir wissen jedoch, dass das Halte-Problem nicht berechenbar ist und daher nicht auf einen solchen Algorithmus A reduziert werden kann.

    Die Grundidee ist, dass es eine Reduktion von A gibt zu B können Sie lernen, dass B mindestens so schwer zu lösen ist wie A und einen mindestens ebenso leistungsfähigen Algorithmus erfordert.

    Wenn also ein Problem A auf ein einfaches Problem B reduziert wird, können wir ableiten, dass A leicht ist (da die Reduktion uns den effizienten Algorithmus gibt) und wenn ein hartes Problem A zu reduziert ist ein Problem B, wir können daraus schließen, dass B auch hart ist (denn wenn B einfach wäre, müsste A auch einfach sein). Es besteht jedoch immer noch die Möglichkeit einer dummen Reduktion von einem einfachen Problem zu einem harten Problem, aber in diesem Fall können wir keine Schlussfolgerungen ziehen.

    28 April 2012
    Polsonby
  • Wenn sich B oder C in NP Complete befinden und alle Probleme in NP auf ein NP-Complete-Problem reduziert werden, kann mit der ersten Regel ein NP-Problem nicht vollständig sein?

    Die erste Regel betrifft Probleme in P. Sie hat nichts mit der Vollständigkeit von NP zu tun. Wenn Problem A NP Complete ist und Problem B auf A reduziert wird, bedeutet nicht , dass B NP Complete ist.

    Wenn A reduziert sich auf B reduziert sich B auf A?

    Nicht generell Nr.

    27 April 2012
    EAMannAndrew