OnlineWoerterBuecher.de
Internes

Lexikon


NP-hard


A set or property of computational {search problem}s. A problem is NP-hard if solving it in {polynomial time} would make it possible to solve all problems in class href="module.php?name=Lexikon&file=search&eid=1&query=NP">NP in polynomial time. Some NP-hard problems are also in href="module.php?name=Lexikon&file=search&eid=1&query=NP">NP (these are called "href="module.php?name=Lexikon&file=search&eid=1&query=NP-complete">NP-complete"), some are not. If you could reduce an href="module.php?name=Lexikon&file=search&eid=1&query=NP">NP problem to an NP-hard problem and then solve it in polynomial time, you could solve all NP problems. See also href="module.php?name=Lexikon&file=search&eid=1&query=computational complexity">computational complexity. [Examples?] (1995-04-10)

In addition suitable contents:
[ href="module.php?name=Lexikon&op=content&tid=134">= ] [ href="module.php?name=Lexikon&op=content&tid=433">al ] [ href="module.php?name=Lexikon&op=content&tid=544">am ] [ href="module.php?name=Lexikon&op=content&tid=592">an ] [ href="module.php?name=Lexikon&op=content&tid=740">ar ] [ href="module.php?name=Lexikon&op=content&tid=743">arc ] [ href="module.php?name=Lexikon&op=content&tid=800">as ] [ href="module.php?name=Lexikon&op=content&tid=894">at ] [ href="module.php?name=Lexikon&op=content&tid=1026">b ] [ href="module.php?name=Lexikon&op=content&tid=1724">ca ] [ href="module.php?name=Lexikon&op=content&tid=2001">ch ] [ href="module.php?name=Lexikon&op=content&tid=2138">cl ] [ href="module.php?name=Lexikon&op=content&tid=2145">class ] [ href="module.php?name=Lexikon&op=content&tid=2247">co ] [ href="module.php?name=Lexikon&op=content&tid=2330">com ] [ href="module.php?name=Lexikon&op=content&tid=2441">complete ] [ href="module.php?name=Lexikon&op=content&tid=2451">complexity ] [ href="module.php?name=Lexikon&op=content&tid=2484">computational complexity ] [ href="module.php?name=Lexikon&op=content&tid=3752">du ] [ href="module.php?name=Lexikon&op=content&tid=3834">E ] [ href="module.php?name=Lexikon&op=content&tid=3896">ed ] [ href="module.php?name=Lexikon&op=content&tid=3923">edu ] [ href="module.php?name=Lexikon&op=content&tid=3929">ee ] [ href="module.php?name=Lexikon&op=content&tid=4148">er ] [ href="module.php?name=Lexikon&op=content&tid=4171">es ] [ href="module.php?name=Lexikon&op=content&tid=4199">et ] [ href="module.php?name=Lexikon&op=content&tid=4497">fi ] [ href="module.php?name=Lexikon&op=content&tid=4520">file ] [ href="module.php?name=Lexikon&op=content&tid=5434">h ] [ href="module.php?name=Lexikon&op=content&tid=5768">hr ] [ href="module.php?name=Lexikon&op=content&tid=5931">id ] [ href="module.php?name=Lexikon&op=content&tid=6013">il ] [ href="module.php?name=Lexikon&op=content&tid=6064">in ] [ href="module.php?name=Lexikon&op=content&tid=6413">io ] [ href="module.php?name=Lexikon&op=content&tid=6482">is ] [ href="module.php?name=Lexikon&op=content&tid=6558">it ] [ href="module.php?name=Lexikon&op=content&tid=6789">ke ] [ href="module.php?name=Lexikon&op=content&tid=6918">la ] [ href="module.php?name=Lexikon&op=content&tid=7023">ld ] [ href="module.php?name=Lexikon&op=content&tid=7091">Lex ] [ href="module.php?name=Lexikon&op=content&tid=7399">ls ] [ href="module.php?name=Lexikon&op=content&tid=7437">lv ] [ href="module.php?name=Lexikon&op=content&tid=7441">ly ] [ href="module.php?name=Lexikon&op=content&tid=7463">ma ] [ href="module.php?name=Lexikon&op=content&tid=8032">mo ] [ href="module.php?name=Lexikon&op=content&tid=8040">mod ] [ href="module.php?name=Lexikon&op=content&tid=8079">module ] [ href="module.php?name=Lexikon&op=content&tid=8167">mp ] [ href="module.php?name=Lexikon&op=content&tid=8228">ms ] [ href="module.php?name=Lexikon&op=content&tid=8384">N ] [ href="module.php?name=Lexikon&op=content&tid=8386">na ] [ href="module.php?name=Lexikon&op=content&tid=8627">ng ] [ href="module.php?name=Lexikon&op=content&tid=8675">no ] [ href="module.php?name=Lexikon&op=content&tid=8744">NP ] [ href="module.php?name=Lexikon&op=content&tid=8747">NP-complete ] [ href="module.php?name=Lexikon&op=content&tid=8964">om ] [ href="module.php?name=Lexikon&op=content&tid=9014">op ] [ href="module.php?name=Lexikon&op=content&tid=9457">pe ] [ href="module.php?name=Lexikon&op=content&tid=9550">ph ] [ href="module.php?name=Lexikon&op=content&tid=9651">pl ] [ href="module.php?name=Lexikon&op=content&tid=9788">polynomial ] [ href="module.php?name=Lexikon&op=content&tid=9908">pr ] [ href="module.php?name=Lexikon&op=content&tid=10253">query ] [ href="module.php?name=Lexikon&op=content&tid=10364">rc ] [ href="module.php?name=Lexikon&op=content&tid=10385">re ] [ href="module.php?name=Lexikon&op=content&tid=10767">ro ] [ href="module.php?name=Lexikon&op=content&tid=10918">S ] [ href="module.php?name=Lexikon&op=content&tid=11150">se ] [ href="module.php?name=Lexikon&op=content&tid=11156">search problem ] [ href="module.php?name=Lexikon&op=content&tid=11281">set ] [ href="module.php?name=Lexikon&op=content&tid=11376">si ] [ href="module.php?name=Lexikon&op=content&tid=11651">so ] [ href="module.php?name=Lexikon&op=content&tid=12588">th ] [ href="module.php?name=Lexikon&op=content&tid=12721">to ] [ href="module.php?name=Lexikon&op=content&tid=13310">ve ] [ href="module.php?name=Lexikon&op=content&tid=13366">vi ]






Go Back ]

Free On-line Dictionary of Computing

Copyright © by OnlineWoerterBuecher.de - (2906 Reads)

All logos and trademarks in this site are property of their respective owner.

Page Generation in 0.0888 Seconds, with 16 Database-Queries
Zurück zur Startseite