View source for Testwiki:Property proposal/Computational complexity

=== {{TranslateThis | anchor = en
| en = computational complexity
}} ===
{{Property proposal
|status			= 10374
|description		= {{TranslateThis
 | en = 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
 | it = la classe di complessità più specifica a cui questo problema computazionale è stato dimostrato appartenere
 }}
|datatype		= wikibase-item
|domain			= {{Q|Q3435924}}
|source			= 
|example		= 
* {{Q|Q1361537}} → {{Q|Q6954626}}
* {{Q|Q1239194}} → {{Q|Q905789}}
* {{Q|Q6042592}} → {{Q|Q215206}}
* {{Q|Q1350285}} → {{Q|Q905967}}
|subpage		= Computational complexity
|topic			= natural science
}}

;Motivation
As done for the [[Wikidata:Property proposal/algorithm complexity|algorithms]], I propose this property for the {{Q|Q908207}} which a {{Q|Q3435924}} may have been proved to belong to. Here a single property is sufficient, because computational complexity is expressed in terms of set membership. --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 18:05, 6 February 2022 (UTC)

;{{int:Talk}}
* {{Ping project|Mathematics}} --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 18:05, 6 February 2022 (UTC)
* {{Ping project|Informatics}} --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 18:06, 6 February 2022 (UTC)
* Why not just "is instance of" "NP-complete problem"? Looks redundant... [[User:Wikisaurus|Wikisaurus]] ([[User talk:Wikisaurus|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 18:08, 6 February 2022 (UTC)
*: {{ping|Wikisaurus}} Redundant with respect to what (notice that the current usage of {{P|P31}} is wrong)? And I think creating an item labelled "X problem" for each complexity class "X" it would be a far worse solution. --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 18:15, 6 February 2022 (UTC)
*::Furthermore, you would still need this property for stating that <"X problem" has complexity "X">. --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 09:41, 7 February 2022 (UTC)
*:::{{ping|Horcrux}} look at the definition of en wiki. You have something like « a problem is NP-complete if » … which states that in effect this is a characterisation of a problem. Basically this is exactly what the « instance » relationship in OWL or other ontology languages defines :&nbsp; the class is a predicate. Here we have a predicate that applies to algorithmic problems. The « instance of » relationship states exactly that the object satisfies the predicate. <span style="border: 1px #C9C9C9;"><span style="background-color:#E8E8E8;padding:3px;">author&nbsp;</span><span style="background-color:#FFFFFF;">&nbsp;[[User:TomT0m|TomT0m]] / </span>talk [[User talk:TomT0m|page]]</span> 10:34, 8 February 2022 (UTC)
*::::{{ping|TomT0m}} Sorry but I don't think this is completely exact. If you were true, then "NP-complete" and "NP-complete problem" would be synonyms, and a sentence like "<math>p</math> is an NP-complete" would be as meaningful as "<math>p</math> is an NP-complete problem" (while it is certainly not the case). The key stands in the article "a" :-)
*::::By definition, despite the name, a complexity class is a '''set''' of problems, not a '''class''' (in the ontological sense) of problems. Therefore, a problem is a member (not an instance) of a class. As evidence of this, notice that, when you don't know if a problem is complete for a certain complexity class, you say that it is '''in''' that class (e.g., standard CQ evaluation is '''in''' AC<math>^0</math> in data complexity) or that it '''belongs''' to that class, or, again, that it is a '''member''' of that class. In other words, the closest semantic relation is the [[:en:Meronymy|meronymy]] and the (current) closest Wikidata property is {{p|361}}. Anyway, I wouldn't use such property for mathematical concepts, since it is not very clear to me if it should be used for set containment (<math>\subseteq</math>) or membership (<math>\in</math>).
*::::However, IMHO this ambiguity makes even more necessary the creation of a separate property. --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 12:04, 8 February 2022 (UTC)
*:::::@[[User:Horcrux|Horcrux]] No, meronymy is out of scope. Wether a class or a set (defined in extension), in maths and in ontology, are characterised by a kind of logical predicate, always. 
*:::::An element/object belongs to the set of class if it satifies the predicate. A complexity class has a logical definition, we decide if a problem is or is not in the class by wether or not the predicate is satisfied 
*:::::In math and ontology it’s the same. The predicates : 
*:::::* A « mobile phone » is a phone that communicates wirelessly 
*:::::* An NP-complete problem is a problem solvable with a Non-deterministic turing machine in polynomial time from which there is a polynomial reduction from any NP-problem
*:::::In both case we can take an object and decide if it belongs in the class by checking the predicate.
*:::::Considering the label in english ''NP-complete'' versus ''NP-completeness'' please notice that the english Wikipedia is titled ''NP-completeness'' and begins with ''An NP-complete problem'' … we are not really at the level of precision of vocabulary when pedanticity really matters, and I’m not even talking about the consistency with other wikipedias. We can choose whatever is OK in Wikidata. <span style="border: 1px #C9C9C9;"><span style="background-color:#E8E8E8;padding:3px;">author&nbsp;</span><span style="background-color:#FFFFFF;">&nbsp;[[User:TomT0m|TomT0m]] / </span>talk [[User talk:TomT0m|page]]</span> 15:20, 9 February 2022 (UTC)
*::::::{{ping|TomT0m}} It depends on how you define the predicate. If you want to express the fact that Bill lives in London you could even define an unary predicate London(x) in your ontology. In this case, Bill will be an instance of the predicate London. This would be logically correct too, but it doesn't describe very well our domain of knowledge. --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 16:19, 9 February 2022 (UTC) 
*:::::::@[[User:Horcrux|Horcrux]] Except my examples made sense. <span style="border: 1px #C9C9C9;"><span style="background-color:#E8E8E8;padding:3px;">author&nbsp;</span><span style="background-color:#FFFFFF;">&nbsp;[[User:TomT0m|TomT0m]] / </span>talk [[User talk:TomT0m|page]]</span> 16:21, 9 February 2022 (UTC)
*:::::To answer about the « set membership » / « set inclusion » problematics, here is the deal. There are layers in the question.
*:::::* A specific problem : « compute the sum of 23 and 25 » let’s call him I
*:::::* An « algorithmic problem », is a set/class of those specific problem. The sum problem « compute the sum of two given numbers ». Let’s call it S
*:::::* I is an example of problem of the kind S . We usually is CS call I an instance of S. The terminology match :&nbsp;{{C|I|instance of|S}}. 
*:::::* S is an example of algorithmic problem. We have {{C|S|instance of|algorithmic problem}}
*:::::* Complexity theory classifies algorithmic problems like S, not instances like I. For example a problem can be, or not, in class P. It is by definition if there is an algorithm that solves any of its instances in polynomial time of the size of the instance. We clearly have a class definition here. It’s even called « a complexity class ». A complexity class is a subclass of « algorithmic problem ». We have
*:::::*: {{C|P-complexity class|subclass of|algorithmic problem}}
*:::::We have clearly that S is in P, this means :
*:::::*: {{C|S|instance of|P-complexity class}}
*:::::There is clear motivation for when to use {{instance of}} and {{subclass of}} in this case.
*:::::Just for the exercises, take a subproblem of S , Ssub : the sum of A and B, where A is pair
*:::::: The set of instances of Ssub in a subset of S. As any instance of Ssub is an instance of S, we have by definition
*:::::: {{C|Ssub|subclass of|S}}
*:::::Ssub cannot be harder than S, so S is clearly in P as well. It might not be P-complete as it could be easier.
*:::::There is no modelisation problem whatsover here. If we say that S is a P problem in Wikidata by
*:::::{{C|S|instance of|P complexity class}} if we also have 
*:::::{{C|P|subclass of|algorithmic problem}} this entails {{C|S|instance of|algorithmic problem}} so we can spare this last statement. <span style="border: 1px #C9C9C9;"><span style="background-color:#E8E8E8;padding:3px;">author&nbsp;</span><span style="background-color:#FFFFFF;">&nbsp;[[User:TomT0m|TomT0m]] / </span>talk [[User talk:TomT0m|page]]</span> 20:06, 9 February 2022 (UTC)
*::::::Your argument is only self-consistent, because you are [[:en:Begging the question|assuming the conclusion]]. The point is exactly that IMHO {{C|P-complexity class|subclass of|algorithmic problem}} is a wrong statement. And, by the way, you can start from this wrong assumption only because you are the one that made [https://www.wikidata.org/w/index.php?title=Q215206&diff=254799088&oldid=252785798 such edits]. Out of Wikidata, {{Q|Q215206}} is an [[:en:Equivalence class|equivalence class]] (i.e., a set), not a class in the ontological sense.
*::::::My example showed that if you are able to express a property with an unary predicate, it doesn't mean that you should do it. Here's other (I hope more meaningful for you) examples.
*::::::* We can say that the Statue of Liberty is blue (or that it is a blue statue). In logic, we could express it as Blue(SoL), but we don't want to say that the Statue of Liberty is an instance of blue (while "instance of blue statue" would be certainly meaningful). Instead, we say that it has a certain {{p|462}}.
*::::::* We can say that The Clash are punk rock (or that they are a punk rock band). In logic, we could express it as PunkRock(theClash), but we don't want to say that The Clash is an instance of punk rock (while "instance of punk rock band" would be certainly meaningful). Instead, we say that they play a certain {{p|P136}}.
*::::::* Analogously, we say that SAT is coNP-complete (or that it is a coNP-complete problem). In logic, we could express it as coNP-c(sat), but we don't want to say that SAT is instance of coNP-complete (while "instance of coNP-complete problem" would be certainly meaningful). Instead, we say that SAT has a certain computational complexity.
*::::::--[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 11:56, 10 February 2022 (UTC)
*:::::::@[[User:Horcrux|Horcrux]] It is a class in the ontological sense and it is in no way incompatible with being a class. It is totally a case of a class that classifies problem according to a certain notion of complexity. An equivalence class is definitely a class, defined by a certain relation. And being a class in math is definitely not incompatible with being a set as discussed before.
*:::::::* We can’t really say that the clash are punk rock, although arguably we could, because it’s a band that performs punk-rock music. We call certain classes of artworks « genre ». The primary purpose of classification is to divide stuffs according to certain chosen criteria. Classifying music by genre is just a special case of those criteria.
*:::::::Anyway, all I say is that these abstract stuffs about classification are not incompatible with a « genre » or a complexity class property, especially if you decide that you classify music by genre and want to link bands to the kind of music they make. But in that specific case, we classify problems according to a certain notion of difficulty to solve, this is not necessary. <span style="border: 1px #C9C9C9;"><span style="background-color:#E8E8E8;padding:3px;">author&nbsp;</span><span style="background-color:#FFFFFF;">&nbsp;[[User:TomT0m|TomT0m]] / </span>talk [[User talk:TomT0m|page]]</span> 14:26, 19 February 2022 (UTC)
*{{s}} seems reasonable to me and it keeps P31 uncluttered --[[User:So9q|So9q]] ([[User talk:So9q|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 13:11, 7 February 2022 (UTC)
* {{ss}} Seems like highly appropriate information to capture. --[[User:SilentSpike|SilentSpike]] ([[User talk:SilentSpike|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 16:36, 7 February 2022 (UTC)
* {{comment}} This seems like a good proposal, but can somebody clarify how the proposed term relates to and differs from {{P|P3752}}, {{P|P3753}}, {{P|P3754}}, {{P|P3755}}, etc.? —'''[[User:The-erinaceous-one|<span style="color: SaddleBrown ;"> The Erinaceous One 🦔</span>]]''' 08:33, 9 February 2022 (UTC)
*:{{ping|The-erinaceous-one}} Well, the point that they have in common is that, for estimating their complexity, we usually consider the worst-case scenario, like in the first and last properties that you mentioned. The difference is that, intuitively, algorithms are procedural while problems are declarative. You usually define a problem in terms of what you want to get or verify, while an algorithm is defined in terms of input, procedure and output. For solving a problem you can have in general many algorithms, and the one with the lowest cost establishes the most accurate upper bound for the problem's complexity. Moreover, notice that, beside the intuitive complexities as LOGSPACE, PTIME or EXPTIME, in general you cannot define them just using a function of the input (take a look at [[:en:List of complexity classes]]). Please forgive my lack of accuracy, I wanted to be more understandable than rigorous. --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 12:03, 10 February 2022 (UTC)
*:{{s}} Thanks, [[User:Horcrux|Horcrux]]. This sounds like a very interesting property. When this property is created, we should like {{P|P3752}}, {{P|P3753}}, etc., under "see also."  —'''[[User:The-erinaceous-one|<span style="color: SaddleBrown ;"> The Erinaceous One 🦔</span>]]''' 23:09, 11 February 2022 (UTC)
* {{support}} I had the same question as [[User:The-erinaceous-one|<span style="color: SaddleBrown ;"> The Erinaceous One 🦔</span>]] so thanks for the above answer - basically this property has domain "computational problem" while the others are for specific algorithms. Clearly the two issues are closely related but not the same. [[User:ArthurPSmith|ArthurPSmith]] ([[User talk:ArthurPSmith|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 20:23, 10 February 2022 (UTC)
* {{support}} Different from the other computational complexities (as a formula) and also a better representation than using {{P|P31}}. --[[User:SlowByte|SlowByte]] ([[User talk:SlowByte|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 12:56, 15 February 2022 (UTC)
: {{ping|Horcrux|Wikisaurus|TomT0m|So9q}} {{ping|SilentSpike|The-erinaceous-one|ArthurPSmith|SlowByte}} {{done}} {{p|10374}} [[User:Pamputt|Pamputt]] ([[User talk:Pamputt|<span class="signature-talk">{{int:Talkpagelinktext}}</span>]]) 11:57, 19 February 2022 (UTC)