Übersetzung für 'NP-schwer' von Deutsch nach Englisch

NP-schwer

NP-hard {adj} [non-deterministic polynomial-time hard]comp.math.

• Ratner und Warmuth bewiesen 1990, dass das verallgemeinerte Problem, die minimale Anzahl Züge zu einer lösbaren Start-Anordnung in einem "n x n -"Spiel zu finden, NP-schwer ist.
• In der Komplexitätstheorie wird die Zeitklasse jener Entscheidungsprobleme als NP-schwer bezeichnet.
• Das Inferenzproblem, sowohl das exakte wie auch das approximative, in Bayes’schen Netzen ist NP-schwer.
• Da 3KNF-SAT NP-schwer ist, gilt dies dann auch für CLIQUE.
• auf das Cliquenproblem, das Rucksackproblem und auf den gerichteten Hamiltonkreis (DHC) polynomiell reduzieren, wodurch auch diese Probleme als NP-schwer nachgewiesen sind.

• Das exakte Finden solcher Teilmengen gilt als algorithmisch schwierig und ist im Allgemeinen NP-schwer.
• Da die Suche nach der optimalen Lösung schwer ist (NP-schwer), wird im Normalfall ein approximativer Algorithmus verwendet wie die Heuristiken von Lloyd oder MacQueen.
• In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist.
• Wie 2005 gezeigt wurde, ist die Frage, ob bei gegebenem Feld, gegebener Roboteranzahl und gegebener Startkonfiguration ein Lösungsweg für irgendeinen Roboter existiert, NP-schwer (s. Weblinks).
• Im Unterschied zur linearen Programmierung ist allerdings das zugrundeliegende Polyeder meist nicht genau bekannt, was das Problem aus komplexitätstheoretischer Sicht NP-schwer macht.

• Spieltheoretiker haben herausgefunden, dass diese Variante sogar NP-schwer ist.
• Im Gegensatz zum Problem des kürzesten Pfades, ist das Problem des längsten Pfades sogar für ungewichtete Graphen NP-schwer.
• Formal ist ein Suchproblem NP-äquivalent, wenn es NP-leicht und NP-schwer ist.
• Die Vielzahl an kombinierbaren Varianten bilden zusammen die "Familie der TSP" – die alle als NP-schwer gelten.
• Trotzdem ist auch für planare Graphen das Bestimmen der chromatischen Zahl NP-schwer.

• Das oben beschriebene Entscheidungsproblem ist NP-vollständig; das zugehörige Optimierungsproblem – das Finden einer Zuordnung, bei der die Anzahl an Behältern minimiert wird – ist NP-schwer.