computational complexity

the most specific complexity class this computational problem has been proved to belong to; if available, provide the tight complexity, otherwise both hardness and membership can be specified
rdfs:label
"computational complexity"@en
skos:altLabel
"complexity class"@en
"computational complexity class"@en
schema:description
"the most specific complexity class this computational problem has been proved to belong to; if available, provide the tight complexity, otherwise both hardness and membership can be specified"@en
schema:dateModified "2025-06-15T15:26:37+00:00"^^xsd:dateTime
schema:version 2361432212
wikibase:claim p:P10374
wikibase:directClaim wdt:P10374
wikibase:novalue p:novalue/P10374
wikibase:propertyType wikibase:WikibaseItem
wikibase:qualifier p:qualifier/P10374
wikibase:qualifierValue p:qualifier/value/P10374
wikibase:reference p:reference/P10374
wikibase:referenceValue p:reference/value/P10374
wikibase:statementProperty p:statement/P10374
wikibase:statementValue p:statement/value/P10374
wikibase:statements 23
p:P1629 wd:statement/P10374-6dabd8cd-4c61-7d90-65e3-8febe07eebcb
p:P1659 wd:statement/P10374-55fd85e2-468f-880a-96b2-b445b6d5360b
wd:statement/P10374-b0990e01-4ea4-e724-a537-645fbf7cd325
wd:statement/P10374-c642f2f3-4bac-2f4d-4efb-d9c5edf85782
wd:statement/P10374-ca069c0e-4f68-f478-5b2c-14a217ef2eb6
wd:statement/P10374-ceb69eda-47b8-a123-64b8-7ef2616e5d4d
wd:statement/P10374-ec555c41-4668-dba9-e8f0-7c30e41139d0
p:P1855 wd:statement/P10374-1a02483e-4af9-0290-4eb9-9ce919da8f46
wd:statement/P10374-34a262be-455f-d22d-481b-3172ecef8266
wd:statement/P10374-ba69e843-4b70-1fb2-b2dc-3579f0bb30d5
wd:statement/P10374-d93c483c-4a3b-fc2d-6c31-ad9380550f0c
p:P2302 wd:statement/P10374-448b5951-45ac-7fcd-4bd0-2c0696cbedac
wd:statement/P10374-52cefd34-4488-4f9a-4c72-dab0ff20e466
wd:statement/P10374-6d02d423-4184-e197-b66c-5f04eba5ca8f
wd:statement/P10374-952d1e0d-41f7-7ec1-b5f5-8d1003700753
wd:statement/P10374-9cf52aeb-43bd-9180-1813-e30855bd06a5
wd:statement/P10374-dee8a721-47da-1919-fcb2-4d73d649b9b8
wd:statement/P10374-eb812ed9-4ade-d68c-aadb-0a82634ed679
p:P31 wd:statement/P10374-0990939f-4482-a257-c7c5-fceb6591cf0c
wd:statement/P10374-8921eb2f-4e92-5e9f-9a42-899cdeac69b0
p:P3254 wd:statement/P10374-04388356-4d26-f60a-e1e0-060bd42ae01b
p:P6104 wd:statement/P10374-53E88E9A-3EC9-479F-B9F5-3A209D36F8CD
wd:statement/P10374-c7bb23f0-494e-4f4c-b988-e62ba118bfc9
wdt:P1629 computational complexity
wdt:P1659 worst-case time complexity
best-case time complexity
average time complexity
worst-case space complexity
best-case space complexity
average space complexity
wdt:P1855 Horn-satisfiability
true quantified Boolean formula
st-connectivity
integer programming
wdt:P2302 single-value constraint
subject type constraint
value-type constraint
allowed-entity-types constraint
property scope constraint
citation-needed constraint
wdt:P31 Wikidata property related to mathematics
Wikidata property related to computing
wdt:P3254 <https://www.wikidata.org/wiki/Wikidata:Property_proposal/Computational_complexity>
wdt:P6104 WikiProject Computer Science
WikiProject Mathematics
Download as:
TurtleJSON-LDRDF/XML
data from SPARQL profile: Wikidata