A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
NP-úplný problém je taký problém, ktorý patrí do triedy NP (je vypočítateľný v nedeterministickom polynomiálnom čase) a ľubovoľný iný problém z triedy NP je naň polynomiálne redukovateľný (tzn. je NP-ťažký). NP-úplné problémy v istom zmysle reprezentujú tie najťažšie problémy spomedzi triedy NP. Pokiaľ by niekto našiel deterministický polynomiálny algoritmus pre jeden NP-úplný problém, vďaka existujúcej redukcii by boli všetky problémy z triedy NP riešiteľné v deterministickom polynomiálnom čase (P=NP).
Častou chybou je interpretácia skratky NP v názve NP-úplný ako nepolynomiálny (ang. non-polynomial), t. j., neriešiteľný v deterministickom polynomiálnom čase. Aj keď sa väčšina odborníkov prikláňa k názoru, že neexistuje deterministický polynomiálny algoritmus pre žiadny NP-úplný problém, toto nebolo nikdy dokázané. Tiež treba dodať, že trieda NP obsahuje všetky problémy ktoré sú riešiteľné v deterministickom polynomiálnom čase.
NP-úplné problémy sú tiež charakteristické tým, že správnosť ich riešenia môže byť overená rýchlo (v deterministickom polynomiálnom čase), ale nie je známa efektívna cesta pre nájdenie riešenia. To znamená, že čas potrebný na riešenie NP-úplného problému rastie asymptoticky rýchlejšie ako polynomiálne (obvykle exponenciálne) vzhľadom na veľkosť zadania (inštancie) problému. Dôsledkom je, že čas potrebný na riešenie aj stredne veľkých inštancií NP-úplných problémov ľahko dosahuje bilióny alebo trilióny rokov pri použití akéhokoľvek množstva dnes dostupného výpočtového výkonu. Aj preto je otázka, či je možné riešiť NP-úplné problémy efektívne jednou z centrálnych otázok počítačovej vedy dneška.
Príklady NP-úplných problémov
- SATISFIABILITY, teda problém splniteľnosti výrokovej formule v konjunktívnej normálnej forme
- 3-SATISFIABILITY, teda problém splniteľnosti výrokovej formule v konjunktívnej normálnej forme, pričom každá klauzula obsahuje najviac tri literály
- Existencia Hamiltonovskej kružnice
- Úloha, či daný graf možno zafarbiť k farbami
- Kvadratická diofantická rovnica
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
AOL Instant Messenger
Apache OpenOffice
Bioinformatika
Build
Cardware
Datagram
Diagram prípadov použitia
Digitálne pero
Django (framework)
Django Framework
EBCDI
Emule
Entita (informatika)
Exabajt
Exbibajt
Fake mailer
Funkcionálne programovanie
Gibibajt
Gigabajt
GNU Lesser General Public License
Graphics Device Interface
H.264/MPEG-4 AVC
Hyperlink
Informatika
Interpreter
Interpreter (programovanie)
Jakarta EE
Java applet
Java ME
Jingle
Kaspersky Anti-Virus
Kibibajt
Kilobajt
Kliknutie
Kompilácia (programovanie)
Kompresný pomer (informatika)
Kontrolný súčet
Lambda kalkul
LibreOffice Writer
LogMeIn Hamachi
Manažment služieb IT
McAfee VirusScan
Mebibajt
Megabajt
Mozilla Corporation
Mozilla Thunderbird
Musical Instrument Digital Interface
NP-úplný problém
Objektovo orientované programovanie
OLAP kocka
OpenID
Pažravý algoritmus
Pebibajt
Petabajt
Polynomiálna transformovateľnosť
Portable Network Graphics
Printer Command Language
Programovanie (informatika)
Program Information File
Redukcia (teoretická informatika)
RGBA
Súbor dát
Spúšťateľný program
Stavový diagram UML
Subpixel
Syntaktická analýza
Tebibajt
Terabajt
Token (text)
Total Commander
TrueSpace
Very High Speed Digital Subscriber Line 2
Virtual Console
Virus Bulletin
Vuze
Weighted RED
Windows Live Messenger
XM
Yobibajt
Yottabajt
Zabezpečený hypertextový prenosový protokol
Zebibajt
Zettabajt
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk