English Explanatory Dictionary

NP-complete

English dictionary entry

Meanings

adj
  1. That is both NP (solvable in polynomial time by a non-deterministic Turing machine) and NP-hard (such that any (other) NP problem can be reduced to it in polynomial time).

Word forms

NP-complete

Related words

NP NP-C NPC NP-completeness NP-easy NP-equivalent NP-hard
This entry uses open data from Wiktionary (CC BY-SA/GFDL). Word forms are used for search and are not indexed as separate pages.
Back to search All on N Russian dictionary Dahl dictionary