Up (Komplexität)

Im Komplexitätstheorie, HOCH (Eindeutige nicht deterministische Polynomzeit) ist der Komplexitätsklasse von Entscheidungsprobleme lösbar in Polynomzeit auf an Eindeutige Turing -Maschine mit höchstens einen akzeptieren Pfad für jeden Eingang. HOCH enthält P und ist in enthalten in Np.

Eine gemeinsame Umformulierung von Np gibt an, dass eine Sprache in ist Np Wenn und nur wenn eine bestimmte Antwort in der Polynomzeit durch eine deterministische Maschine überprüft werden kann. Ebenso ist eine Sprache in HOCH Wenn eine bestimmte Antwort in der Polynomzeit verifiziert werden kann und die Verifiermaschine höchstens akzeptiert werden eines Antwort für jede Probleminstanz. Formell eine Sprache, eine Sprache L gehört HOCH Wenn es einen Polynom-Zeit-Algorithmus mit zwei Eingängen gibt A und eine Konstante c so dass

Wenn x in L Dann gibt es ein einzigartiges Zertifikat y mit ${\ displayStyle | y | = o (| x |^{c})}$ so dass ${\ displayStyle a (x, y) = 1}$

Wenn X nicht in ist LEs gibt kein Zertifikat y mit ${\ displayStyle | y | = o (| x |^{c})}$ so dass ${\ displayStyle a (x, y) = 1}$

Algorithmus A überprüft L in Polynomzeit.

HOCH (und sein ergänzen Coup) enthalten beide Ganzzahlfaktorisierung Problem und Paritätsspiel Problem; Da entschlossene Anstrengungen noch keine Polynom-Zeit-Lösung für eines dieser Probleme gefunden haben, wird vermutet, dass es schwer zu zeigen ist P=HOCH, oder auch P= (HOCH ∩ Coup).

Das Valiant -Vazirani -Theorem besagt, dass Np ist in RP^Versprechen, was bedeutet, dass es eine randomisierte Reduktion von jedem Problem in gibt Np zu einem Problem in Versprechen.

HOCH ist nicht bekannt, dass es welche hat Komplett Probleme.^[1]

Verweise

Verweise

• Lane A. Hemaspaandra und Jorg Rothe, Eindeutige Berechnung: Boolesche Hierarchien und spärliche Turing-Sets, Siam J. Comput., 26 (3) (Juni 1997), 634–653