Property talk:P10374

Documentation

• Start a query
• Current uses
• Statistics by class
• List of values
• List of qualifiers
• Count

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

Represents	computational complexity (Q5157286)
Data type	Item
Domain	computational problem (Q3435924)
Example	st-connectivity (Q1361537) → NL-complete (Q6954626) Horn-satisfiability (Q1239194) → P-complete (Q905789) Integer programming (Q6042592) → NP-complete (Q215206) true quantified Boolean formula (Q1350285) → PSPACE-complete (Q905967)
See also	worst-case time complexity (P3752), best-case time complexity (P3753), average time complexity (P3754), worst-case space complexity (P3755), best-case space complexity (P3756), average space complexity (P3757)
Lists	Items with the most statements of this property Count of items by number of statements (chart) Items with the most statements Items with the fewest statements Count of items by number of sitelinks (chart) Items with the most sitelinks Items with the most sitelinks, but no link to one Wikipedia (sample: Welsh Wikipedia, cywiki) Items with the fewest sitelinks Most linked wikis Items with the most identifier properties By value of property Most statements Fewest statements Most sitelinks Most linked wikis Total of sitelinks on items Most identifiers Fewest identifiers Items with no other statements Most recently created items Items with novalue claims Items with unknown value claims Usage history (total) Usage history (main statement) Database reports/Constraint violations/P10374 Map Random list
Proposal discussion	Proposal discussion
Current uses	Total 89 Main statement 85 95.5% of uses Qualifier 4 4.5% of uses
Search for values

[create Create a translatable help page (preferably in English) for this property to be included here]

Type “computational problem (Q3435924)”: item must contain property “instance of (P31), subclass of (P279)” with classes “computational problem (Q3435924)” or their subclasses (defined using subclass of (P279)). (Help)

Exceptions are possible as rare values may exist. Exceptions can be specified using exception to constraint (P2303).
List of violations of this constraint: Database reports/Constraint violations/P10374#Type Q3435924, SPARQL

Value type “complexity class (Q908207)”: This property should use items as value that contain property “instance of (P31)”. On these, the value for instance of (P31) should be an item that uses subclass of (P279) with value complexity class (Q908207) (or a subclass thereof). (Help)

Exceptions are possible as rare values may exist. Exceptions can be specified using exception to constraint (P2303).
List of violations of this constraint: Database reports/Constraint violations/P10374#Value type Q908207, SPARQL

Citation needed: the property must have at least one reference (Help)

Exceptions are possible as rare values may exist. Exceptions can be specified using exception to constraint (P2303).
List of violations of this constraint: Database reports/Constraint violations/P10374#citation needed

Allowed entity types are Wikibase item (Q29934200): the property may only be used on a certain entity type (Help)

Exceptions are possible as rare values may exist. Exceptions can be specified using exception to constraint (P2303).
List of violations of this constraint: Database reports/Constraint violations/P10374#Entity types

Scope is as main value (Q54828448): the property must be used by specified way only (Help)

Exceptions are possible as rare values may exist. Exceptions can be specified using exception to constraint (P2303).
List of violations of this constraint: Database reports/Constraint violations/P10374#Scope, SPARQL

Single value: this property generally contains a single value. (Help)

Exceptions are possible as rare values may exist. Exceptions can be specified using exception to constraint (P2303).
List of violations of this constraint: Database reports/Constraint violations/P10374#Single value, SPARQL