See NP-complete in All languages combined, or Wiktionary
Download JSON data for NP-complete meaning in English (4.4kB)
{
"head_templates": [
{
"args": {
"1": "-"
},
"expansion": "NP-complete (not comparable)",
"name": "en-adj"
}
],
"lang": "English",
"lang_code": "en",
"pos": "adj",
"senses": [
{
"categories": [
{
"kind": "other",
"name": "English entries with incorrect language header",
"parents": [
"Entries with incorrect language header",
"Entry maintenance"
],
"source": "w"
},
{
"kind": "other",
"name": "Georgian terms with redundant script codes",
"parents": [
"Terms with redundant script codes",
"Entry maintenance"
],
"source": "w"
},
{
"kind": "topical",
"langcode": "en",
"name": "Theory of computing",
"orig": "en:Theory of computing",
"parents": [
"Computer science",
"Computing",
"Sciences",
"Technology",
"All topics",
"Fundamental"
],
"source": "w"
}
],
"examples": [
{
"ref": "2001, Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, Introduction To Algorithms, 2nd edition, The MIT Press, page 968",
"text": "Informally, a problem is in the class NPC—and we refer to it as being NP-complete—if it is in NP and is as \"hard\" as any problem in NP. We shall formally define what it means to be as hard as any problem in NP later in this chapter. In the meantime, we will state without proof that if any NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. Most theoretical computer scientists believe that the NP-complete problems are intractable, since given the wide range of NP-complete problems that have been studied to date—without anyone having discovered a polynomial-time solution to any of them—it would be truly astounding if all of them could be solved in polynomial time. Yet, given the effort devoted thus far to proving NP-complete problems intractable—without a conclusive outcome—we cannot rule out the possibility that the NP-complete problems are in fact solvable in polynomial time.",
"type": "quotation"
},
{
"ref": "2002, Thomas A. Garrity, All the Mathematics You Missed: But Need to Know for Graduate School, Cambridge University Press, page 317",
"text": "Every area of math seems to have its own NP complete problems. For example, the question of whether or not a graph contains a Hamiltonian circuit is a quintessential NP complete problem and, since it can be explained with little higher level math, is a popular choice in expository works.",
"type": "quotation"
},
{
"ref": "2003, A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Volume A, Springer, page 43",
"text": "A problem Π is said to be NP-complete if each problem in NP is reducible to Π. Hence\n(4.13) if some NP-complete problem belongs to P, then P=NP.",
"type": "quotation"
}
],
"glosses": [
"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)."
],
"id": "en-NP-complete-en-adj-sLcx1ivp",
"links": [
[
"computing",
"computing#Noun"
],
[
"theory",
"theory"
],
[
"decision problem",
"decision problem"
],
[
"NP",
"NP"
],
[
"NP-hard",
"NP-hard"
]
],
"raw_glosses": [
"(computing theory, of a decision problem) 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)."
],
"raw_tags": [
"of a decision problem"
],
"related": [
{
"word": "NP"
},
{
"english": "the set of NP-complete problems",
"word": "NP-C"
},
{
"english": "the set of NP-complete problems",
"word": "NPC"
},
{
"word": "NP-completeness"
},
{
"word": "NP-hard"
},
{
"word": "NP-easy"
},
{
"word": "NP-equivalent"
}
],
"tags": [
"not-comparable"
],
"topics": [
"computing",
"computing-theory",
"engineering",
"mathematics",
"natural-sciences",
"physical-sciences",
"sciences"
],
"translations": [
{
"code": "nl",
"lang": "Dutch",
"sense": "both NP and NP-hard",
"word": "NP-volledig"
},
{
"code": "nl",
"lang": "Dutch",
"sense": "both NP and NP-hard",
"word": "NP-compleet"
},
{
"code": "fi",
"lang": "Finnish",
"sense": "both NP and NP-hard",
"word": "NP-täydellinen"
},
{
"code": "fr",
"lang": "French",
"sense": "both NP and NP-hard",
"word": "NP-complet"
},
{
"code": "ka",
"lang": "Georgian",
"roman": "NP-sruli",
"sense": "both NP and NP-hard",
"word": "NP-სრული"
},
{
"code": "de",
"lang": "German",
"sense": "both NP and NP-hard",
"word": "NP-vollständig"
},
{
"code": "pt",
"lang": "Portuguese",
"sense": "both NP and NP-hard",
"tags": [
"masculine"
],
"word": "NP-completo"
}
],
"wikipedia": [
"NP-completeness"
]
}
],
"word": "NP-complete"
}
{
"head_templates": [
{
"args": {
"1": "-"
},
"expansion": "NP-complete (not comparable)",
"name": "en-adj"
}
],
"lang": "English",
"lang_code": "en",
"pos": "adj",
"related": [
{
"word": "NP"
},
{
"english": "the set of NP-complete problems",
"word": "NP-C"
},
{
"english": "the set of NP-complete problems",
"word": "NPC"
},
{
"word": "NP-completeness"
},
{
"word": "NP-hard"
},
{
"word": "NP-easy"
},
{
"word": "NP-equivalent"
}
],
"senses": [
{
"categories": [
"English adjectives",
"English entries with incorrect language header",
"English lemmas",
"English multiword terms",
"English terms with quotations",
"English uncomparable adjectives",
"Georgian terms with redundant script codes",
"en:Theory of computing"
],
"examples": [
{
"ref": "2001, Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, Introduction To Algorithms, 2nd edition, The MIT Press, page 968",
"text": "Informally, a problem is in the class NPC—and we refer to it as being NP-complete—if it is in NP and is as \"hard\" as any problem in NP. We shall formally define what it means to be as hard as any problem in NP later in this chapter. In the meantime, we will state without proof that if any NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. Most theoretical computer scientists believe that the NP-complete problems are intractable, since given the wide range of NP-complete problems that have been studied to date—without anyone having discovered a polynomial-time solution to any of them—it would be truly astounding if all of them could be solved in polynomial time. Yet, given the effort devoted thus far to proving NP-complete problems intractable—without a conclusive outcome—we cannot rule out the possibility that the NP-complete problems are in fact solvable in polynomial time.",
"type": "quotation"
},
{
"ref": "2002, Thomas A. Garrity, All the Mathematics You Missed: But Need to Know for Graduate School, Cambridge University Press, page 317",
"text": "Every area of math seems to have its own NP complete problems. For example, the question of whether or not a graph contains a Hamiltonian circuit is a quintessential NP complete problem and, since it can be explained with little higher level math, is a popular choice in expository works.",
"type": "quotation"
},
{
"ref": "2003, A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Volume A, Springer, page 43",
"text": "A problem Π is said to be NP-complete if each problem in NP is reducible to Π. Hence\n(4.13) if some NP-complete problem belongs to P, then P=NP.",
"type": "quotation"
}
],
"glosses": [
"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)."
],
"links": [
[
"computing",
"computing#Noun"
],
[
"theory",
"theory"
],
[
"decision problem",
"decision problem"
],
[
"NP",
"NP"
],
[
"NP-hard",
"NP-hard"
]
],
"raw_glosses": [
"(computing theory, of a decision problem) 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)."
],
"raw_tags": [
"of a decision problem"
],
"tags": [
"not-comparable"
],
"topics": [
"computing",
"computing-theory",
"engineering",
"mathematics",
"natural-sciences",
"physical-sciences",
"sciences"
],
"wikipedia": [
"NP-completeness"
]
}
],
"translations": [
{
"code": "nl",
"lang": "Dutch",
"sense": "both NP and NP-hard",
"word": "NP-volledig"
},
{
"code": "nl",
"lang": "Dutch",
"sense": "both NP and NP-hard",
"word": "NP-compleet"
},
{
"code": "fi",
"lang": "Finnish",
"sense": "both NP and NP-hard",
"word": "NP-täydellinen"
},
{
"code": "fr",
"lang": "French",
"sense": "both NP and NP-hard",
"word": "NP-complet"
},
{
"code": "ka",
"lang": "Georgian",
"roman": "NP-sruli",
"sense": "both NP and NP-hard",
"word": "NP-სრული"
},
{
"code": "de",
"lang": "German",
"sense": "both NP and NP-hard",
"word": "NP-vollständig"
},
{
"code": "pt",
"lang": "Portuguese",
"sense": "both NP and NP-hard",
"tags": [
"masculine"
],
"word": "NP-completo"
}
],
"word": "NP-complete"
}
This page is a part of the kaikki.org machine-readable English dictionary. This dictionary is based on structured data extracted on 2024-04-26 from the enwiktionary dump dated 2024-04-21 using wiktextract (93a6c53 and 21a9316). The data shown on this site has been post-processed and various details (e.g., extra categories) removed, some information disambiguated, and additional data merged from other sources. See the raw data download page for the unprocessed wiktextract data.
If you use this data in academic research, please cite Tatu Ylonen: Wiktextract: Wiktionary as Machine-Readable Structured Data, Proceedings of the 13th Conference on Language Resources and Evaluation (LREC), pp. 1317-1325, Marseille, 20-25 June 2022. Linking to the relevant page(s) under https://kaikki.org would also be greatly appreciated.