NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné všechny ostatní problémy z NP. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty nejtěžší úlohy z NP. Pokud by byl nalezen polynomiální deterministický algoritmus pro nějakou NP-úplnou úlohu, znamenalo by to, že všechny nedeterministicky polynomiální problémy jsou řešitelné v polynomiálním čase, tedy že třída NP se „zhroutí“ do třídy P (NP = P).

PropertyValue
dbpedia-owl:abstract
  • NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné všechny ostatní problémy z NP. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty nejtěžší úlohy z NP. Pokud by byl nalezen polynomiální deterministický algoritmus pro nějakou NP-úplnou úlohu, znamenalo by to, že všechny nedeterministicky polynomiální problémy jsou řešitelné v polynomiálním čase, tedy že třída NP se „zhroutí“ do třídy P (NP = P). Otázka, zda nějaký takový algoritmus existuje, zatím nebyla rozhodnuta, předpokládá se však, že NP ≠ P (je však zřejmé, že P ⊆ NP). Více o tomto problému najdete v článku Problém P versus NP.Vztah mezi P a NP je jedním ze sedmi problémů tisíciletí, které vypsal Clayův matematický ústav 24. května 2000. Za rozhodnutí vztahu nabízí 1 000 000 dolarů.
dbpedia-owl:wikiPageID
  • 7176 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 2190 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 23 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 13974387 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
dbpedia-owl:wikiPageWikiLinkText
  • NP-úplná
  • NP-úplné
  • NP-úplných
  • NP-úplnost
  • NP-úplným problémem
  • NP-těžký
  • NP-úplný
  • NP-úplným
  • NP úplný
dcterms:subject
rdfs:comment
  • NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné všechny ostatní problémy z NP. To znamená, že třídu NP-úplných úloh tvoří v jistém smyslu ty nejtěžší úlohy z NP. Pokud by byl nalezen polynomiální deterministický algoritmus pro nějakou NP-úplnou úlohu, znamenalo by to, že všechny nedeterministicky polynomiální problémy jsou řešitelné v polynomiálním čase, tedy že třída NP se „zhroutí“ do třídy P (NP = P).
rdfs:label
  • NP-úplnost
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageDisambiguates of
is dbpedia-owl:wikiPageRedirects of
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of