NP-äquivalent

NP-äquivalent

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:

  • Äquivalént — (lat., »gleichgeltend«), als Hauptwort: Gegenstand von gleichem Wert. – In der Chemie sind Äquivalente (Äquivalentgewichte) diejenigen relativen Mengen chemischer Körper, die von einem gewissen Gesichtspunkt aus gleichwertig erscheinen und in… …   Meyers Großes Konversations-Lexikon

  • Äquivalént — (lat.), gleich an Wert; der Wert oder die Summe, welche als Ersatz oder Entschädigung gegeben wird. In der Chemie heißen diejenigen relativen Mengen von Substanz äquivalent, die in gewissen Fällen gleiche Wirkung hervorzubringen vermögen;… …   Kleines Konversations-Lexikon

  • äquivalent — Adj gleichwertig per. Wortschatz fach. (17. Jh.) Entlehnung. Entlehnt aus frz. équivalent und relatinisiert nach ml. aequivalens ( entis), dieses aus l. aequus gleich und l. valēns ( entis) kräfig, vermögend , zu l. valēre wert sein, bei Kräften… …   Etymologisches Wörterbuch der deutschen sprache

  • äquivalent — Adj. (Oberstufe) geh.: von gleichem Wert Synonyme: entsprechend, gleichwertig Beispiel: Ein tausendstel Gramm der Materie ist äquivalent zu 25 000 Kilowattstunden. Kollokation: eine äquivalente Ausbildung …   Extremes Deutsch

  • Äquivalent — (v. lat.), 1) Entschädigung, Ausgleichungssumme; 2) Chemisches Ä., so v.w. Atom, s.d.; Endosmotisches Ä., s. Endosmose; Mechanisches Ä. der Wärme, s. Wärme …   Pierer's Universal-Lexikon

  • Äquivalent — Äquivalent …   Deutsch Wörterbuch

  • äquivalent — gleichartig; gleich beschaffen; gleichwirkend * * * äqui|va|lẹnt 〈[ va ] Adj.〉 gleichwertig [<lat. aequus „gleich“ + valere „wert sein, gelten“] * * * Ä|qui|va|lẹnt [↑ äqui u. ↑ valent], das; s, e: Kurzbez. für Äquival …   Universal-Lexikon

  • Äquivalent — gleichwertiger Ersatz * * * äqui|va|lẹnt 〈[ va ] Adj.〉 gleichwertig [<lat. aequus „gleich“ + valere „wert sein, gelten“] * * * Ä|qui|va|lẹnt [↑ äqui u. ↑ valent], das; s, e: Kurzbez. für Äquivalentteilchen als (gedachter) Bruchteil 1/z*… …   Universal-Lexikon

  • Äquivalent — das Äquivalent, e (Aufbaustufe) geh.: etw., was den gleichen Wert wie eine andere Sache hat Synonyme: Entsprechung, Gegenwert, Ausgleich, Ersatz Beispiele: Das italienische Wort hat kein Äquivalent im Englischen. Wir haben das Geld als Äquivalent …   Extremes Deutsch

  • Äquivalent — Das Wort Äquivalenz (v. lat.: aequus „gleich“ und Valenz „Wertigkeit“) bezeichnet in der Bildungssprache die Gleichwertigkeit verschiedener Dinge. In verschiedenen Fachgebieten bezeichnet Äquivalenz das folgende: In der Informatik gibt es die… …   Deutsch Wikipedia

  • Äquivalent — angemessen, entsprechend, gleichwertig, von entsprechendem/gleichem Wert. * * * äquivalent:⇨gleichwertig(1) Äquivalent(gleichwertiger)Ersatz,Gegenwert,Gegenleistung,Entschädigung,Ausgleich,Abgeltung,Surrogat …   Das Wörterbuch der Synonyme

Share the article and excerpts

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