NP-complete

complexity class
rdfs:label
"NP-complete"@en
skos:altLabel
"CNP"@en
"NPC"@en
"nondeterministic polynomial time-complete"@en
"nondeterministic polynomial time-complete class"@en
schema:description
"complexity class"@en
schema:dateModified "2026-07-10T12:02:53+00:00"^^xsd:dateTime
schema:version 2515853598
wikibase:identifiers 12
wikibase:sitelinks 32
wikibase:statements 27
p:P10037 wd:statement/Q215206-7EF23746-61CF-42FB-9F00-2D16FEBA2F70
p:P10283 wd:statement/Q215206-DA82D75B-5341-4CEF-84BB-D8B27D38D10A
p:P10565 wd:statement/Q215206-B4394AE4-90A3-471A-AEBF-9A76E23D3DBE
p:P1269 wd:statement/Q215206-37aacf4f-4ff3-41be-f95f-11bc5b04e233
p:P14541 wd:statement/Q215206-0DF58D79-40A3-4562-8BDF-8AE217C40CD7
p:P1482 wd:statement/Q215206-233ce85b-4f6c-576c-5ecc-513ccf9b2594
wd:statement/Q215206-98f40d2e-4051-35d8-4d19-de6a172a9773
wd:statement/Q215206-dbf29a9c-48fc-b5cb-013e-6f62c0ab7d63
p:P1552 wd:statement/Q215206-b481999a-44cd-d89f-7f58-5ae2903bca17
p:P18 wd:statement/Q215206-8f1a4ef0-44ef-00ba-400f-d5a9140e2820
p:P279 wd:statement/Q215206-c7a15d75-493f-9f75-bf09-b5ea5a58f542
p:P2812 wd:statement/Q215206-23C60E5C-FDA3-48E1-A914-7111CA40EF6B
p:P31 wd:statement/Q215206-cc7fbe71-40dd-45fe-ca85-f0295d8d1cda
p:P361 wd:statement/Q215206-495f1792-435b-1773-793e-1c311c41a758
wd:statement/Q215206-c4b26ba9-4e4d-a95a-a95c-d713d8767e8f
p:P373 wd:statement/Q215206-cf35c3bf-4c27-e13c-344e-f817f69b5cb4
p:P3847 wd:statement/Q215206-b2629d0f-4ff8-bc0a-3b98-d1fe90e62a8e
p:P5106 wd:statement/Q215206-4963EB3D-3C8E-4C43-B7B8-5AAF48DF7397
p:P527 wd:statement/Q215206-670e6b85-415d-ea43-3904-44ae051cde8f
wd:statement/Q215206-b811305d-4c15-12f4-fcce-0e0705324f80
p:P6104 wd:statement/Q215206-ED6797EF-1FB2-4DAA-B976-39E73832DBE6
p:P6366 wd:statement/Q215206-A6C2699C-8C9B-49E5-A9DD-DC5DB70C920A
p:P646 wd:statement/Q215206-7FE8203F-FA2D-48EF-9CB6-D33D68BA7C47
p:P6781 wd:statement/Q215206-de6e475e-41b4-9b48-aa7a-9db67db1216c
p:P7726 wd:statement/Q215206-85135bd7-4bd0-7da7-d8b4-a33547f35436
p:P910 wd:statement/Q215206-33271758-81DA-4643-8AB3-602371D2DA36
p:P9100 wd:statement/Q215206-9093f240-4e29-116e-1490-ae73bad87268
p:direct-normalized/P6366 <https://makg.org/entity/122749075>
wdt:P10037 "problemi-np-completi"
wdt:P10283 "C122749075"
wdt:P10565 "207239"
wdt:P1269 P versus NP problem
wdt:P14541 "2minu4"
wdt:P1482 <https://cs.stackexchange.com/tags/np-complete>
<https://cstheory.stackexchange.com/tags/np-complete>
<https://stackoverflow.com/tags/np-complete>
wdt:P1552 completeness
wdt:P18 <http://commons.wikimedia.org/wiki/Special:FilePath/P%20np%20np-complete%20np-hard.svg>
wdt:P279 computational problem
wdt:P2812 "NP-CompleteProblem"
wdt:P31 complexity class
wdt:P361 NP-hard
NP
wdt:P373 "NP-complete problems"
wdt:P3847 "np-complete_problems"
wdt:P5106 "npcomplete"
wdt:P527 strong NP-completeness
weak NP-completeness
wdt:P6104 WikiProject Mathematics
wdt:P6366 "122749075"
wdt:P646 "/m/09tkl"
wdt:P6781 "Definition:NP-Complete"
wdt:P7726 "NPcomplete"
wdt:P910 Category:NP-complete problems
wdt:P9100 "np-completeness"
Download as:
TurtleJSON-LDRDF/XML
data from SPARQL profile: Wikidata