NP-Äquivalenz

NP-Äquivalenz

NP-Äquivalenz ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik. Es liefert eine prinzipielle Aussage darüber, ob Suchprobleme mit wachsender Anzahl der zu durchsuchenden Pfade oder Objekte noch praktisch lösbar sind, oder ob der benötigte Zeit- oder Speicheraufwand rasch in makroskopische Dimensionen wächst.

Formal ist ein Suchproblem NP-äquivalent, wenn es NP-leicht und NP-schwer ist. Dies ist genau dann der Fall, wenn das zugehörige Entscheidungsproblem NP-vollständig ist. Ein NP-äquivalentes Problem ist genau dann in polynomieller Zeit lösbar, wenn P=NP ist.


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Äquivalenz (Tontechnik) — Äquivalenz bedeutet in der Tontechnik die Gleichwertigkeit von gleichsinnig wirkenden Δ t Laufzeitdifferenz und Δ L Pegeldifferenz bei den Lautsprechersignalen zur Erzeugung von Phantomschallquellen beim Richtungshören im Stereodreieck, wie es… …   Deutsch Wikipedia

  • Äquivalenz (Patentwesen) — Äquivalenz ist ein Bewertungskriterium für Erfinderische Tätigkeit im Sinne von § 4 PatG. Aus einem anderen Blickwinkel gesehen bezeichnet die Äquivalenz den Schutzbereich des Erfindungsgegenstandes (= das in den Patentansprüchen definierte), der …   Deutsch Wikipedia

  • Äquivalenz (Logik) — Eine logische Äquivalenz liegt vor, wenn zwei logische Ausdrücke den gleichen Wahrheitswert besitzen. Der Ausdruck Äquivalenz wird in der Logik mehrdeutig verwendet: zum einen im Sinne der materialen Äquivalenz (Bikonditional) zum anderen im… …   Deutsch Wikipedia

  • Äquivalenz — Das Wort Äquivalenz (v. lat.: aequus „gleich“ und valere „Wertigkeit“: dt. Gleichwertigkeit) wird im Zusammenhang mit folgenden Sachverhalten verwendet: Mathematik, Logik Äquivalenzrelation das Äquivalenzzeichen: Äquivalenzklasse Logische… …   Deutsch Wikipedia

  • Äquivalenz von Kategorien — Die Kategorientheorie oder die kategorielle Algebra ist ein Zweig der Mathematik, der sich Anfang der 1940er Jahre zuerst im Rahmen der Topologie entwickelte; Saunders MacLane nennt seine 1945 gemeinsam mit Samuel Eilenberg entstandene „General… …   Deutsch Wikipedia

  • Äquivalenz von Masse und Energie — Dieser Artikel wurde den Mitarbeitern der Redaktion Physik zur Qualitätssicherung aufgetragen. Wenn Du Dich mit dem Thema auskennst, bist Du herzlich eingeladen, Dich an der Prüfung und möglichen Verbesserung des Artikels zu beteiligen. Der… …   Deutsch Wikipedia

  • Äquivalenz von Energie und Masse — „Relativitätstheorie“, sechste und letzte Skulptur beim Berliner Walk of Ideas zur FIFA Fußball Weltmeisterschaft in Deutschland 2006 Die Äquivalenz von Masse und Energie ist die Erkenntnis der relativistischen Physik, dass die Energie ERuhe… …   Deutsch Wikipedia

  • Äquivalenz — Gleichwertigkeit; Gegenwert * * * Äqui|va|lẹnz 〈[ va ] f. 20; unz.〉 Gleichwertigkeit [→ äquivalent] * * * Äqui|va|lẹnz, die; , en [mlat. aequivalentia]: 1. (bildungsspr.) Gleichwertigkeit: die Ä. zweier Begriffe, verschiedener Tauscho …   Universal-Lexikon

  • Äquivalenz (Norm) — Dieser Artikel erklärt neben den gleichbedeutenden Begriffen normierter Raum und normierter Vektorraum per Weiterleitung auch die Begriffe Norm (Mathematik), Vektornorm, Halbnorm (Seminorm), Operatornorm, Matrixnorm und Frobeniusnorm. normierter… …   Deutsch Wikipedia

  • Äquivalenz (Matrix) — Die Äquivalenz im mathematischen Teilgebiet der linearen Algebra ist eine Äquivalenzrelation auf der Klasse der Matrizen. Zwei Matrizen A und B sind per Definition äquivalent, wenn es eine lineare Abbildung gibt und es Basen B1,B2 von und …   Deutsch Wikipedia

  • Äquivalenz der phytosanitären Massnahmen — fitosanitarijos priemonių lygiavertiškumas statusas Aprobuotas sritis augalų apsauga ir karantino priemonės apibrėžtis Skirtingų fitosanitarijos priemonių savybė daryti tokį patį poveikį. atitikmenys: angl. equivalence vok. Äquivalenz der… …   Lithuanian dictionary (lietuvių žodynas)

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”