Wikidata:Property proposal/Computational complexity

computational complexity

Originally proposed at Wikidata:Property proposal/Natural science

   Done: computational complexity (P10374) (Talk and documentation)

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
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)

Motivation

As done for the algorithms, I propose this property for the complexity class (Q908207) which a computational problem (Q3435924) may have been proved to belong to. Here a single property is sufficient, because computational complexity is expressed in terms of set membership. --Horcrux (talk) 18:05, 6 February 2022 (UTC)

Discussion

• Opensofias
  Tobias1984
  Arthur Rubin
  Cuvwb
  TomT0m
  Physikerwelt
  Lymantria
  Bigbossfarin
  Infovarius
  Helder
  PhilMINT
  Malore
  Lore.mazza51
  Wikisaurus
  The Anome
  The-erinaceous-one
  Daniel Mietchen
  Haansn08
  Xenmorpha
  John Samuel
  Jeremy Dover
  Toni 001
  Bocardodarapti
  Duckmather
  HTinC23
  fgnievinski
  
  Notified participants of WikiProject Mathematics --Horcrux (talk) 18:05, 6 February 2022 (UTC)
• WikiProject Informatics has more than 50 participants and couldn't be pinged. Please post on the WikiProject's talk page instead. --Horcrux (talk) 18:06, 6 February 2022 (UTC)
• Why not just "is instance of" "NP-complete problem"? Looks redundant... Wikisaurus (talk) 18:08, 6 February 2022 (UTC)

  @Wikisaurus: Redundant with respect to what (notice that the current usage of instance of (P31) is wrong)? And I think creating an item labelled "X problem" for each complexity class "X" it would be a far worse solution. --Horcrux (talk) 18:15, 6 February 2022 (UTC)

  Furthermore, you would still need this property for stating that <"X problem" has complexity "X">. --Horcrux (talk) 09:41, 7 February 2022 (UTC)

  @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 :  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. author  TomT0m / talk page 10:34, 8 February 2022 (UTC)

  @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 "$p$ is an NP-complete" would be as meaningful as "$p$ 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$^{0}$ 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 meronymy and the (current) closest Wikidata property is part of (P361). 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 ($\subseteq$) or membership ($\in$).

  However, IMHO this ambiguity makes even more necessary the creation of a separate property. --Horcrux (talk) 12:04, 8 February 2022 (UTC)

  @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. author  TomT0m / talk page 15:20, 9 February 2022 (UTC)

  @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. --Horcrux (talk) 16:19, 9 February 2022 (UTC)

  @Horcrux Except my examples made sense. author  TomT0m / talk page 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 : 
    ⟨ I ⟩ instance of (P31) ⟨ S ⟩
    .
  • S is an example of algorithmic problem. We have
    ⟨ S ⟩ instance of (P31) ⟨ 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

    ⟨ P-complexity class ⟩ subclass of (P279) ⟨ algorithmic problem ⟩

  We have clearly that S is in P, this means :

  • ⟨ S ⟩ instance of (P31) ⟨ P-complexity class ⟩

  There is clear motivation for when to use instance of (P31) and subclass of (P279) 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

  ⟨ Ssub ⟩ subclass of (P279) ⟨ 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

  ⟨ S ⟩ instance of (P31) ⟨ P complexity class ⟩

  if we also have

  ⟨ P ⟩ subclass of (P279) ⟨ algorithmic problem ⟩

  this entails

  ⟨ S ⟩ instance of (P31) ⟨ algorithmic problem ⟩

  so we can spare this last statement. author  TomT0m / talk page 20:06, 9 February 2022 (UTC)

  Your argument is only self-consistent, because you are assuming the conclusion. The point is exactly that IMHO

  ⟨ P-complexity class ⟩ subclass of (P279) ⟨ 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 such edits. Out of Wikidata, NP-complete (Q215206) is an 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 color (P462).
  • 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 genre (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.

  --Horcrux (talk) 11:56, 10 February 2022 (UTC)

  @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. author  TomT0m / talk page 14:26, 19 February 2022 (UTC)

•  Support seems reasonable to me and it keeps P31 uncluttered --So9q (talk) 13:11, 7 February 2022 (UTC)
•  Strong support Seems like highly appropriate information to capture. --SilentSpike (talk) 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 worst-case time complexity (P3752), best-case time complexity (P3753), average time complexity (P3754), worst-case space complexity (P3755), etc.? — The Erinaceous One 🦔 08:33, 9 February 2022 (UTC)

  @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. --Horcrux (talk) 12:03, 10 February 2022 (UTC)

   Support Thanks, Horcrux. This sounds like a very interesting property. When this property is created, we should like worst-case time complexity (P3752), best-case time complexity (P3753), etc., under "see also." — The Erinaceous One 🦔 23:09, 11 February 2022 (UTC)

•  Support I had the same question as The Erinaceous One 🦔 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. ArthurPSmith (talk) 20:23, 10 February 2022 (UTC)
•  Support Different from the other computational complexities (as a formula) and also a better representation than using instance of (P31). --SlowByte (talk) 12:56, 15 February 2022 (UTC)

@Horcrux, Wikisaurus, TomT0m, So9q: @SilentSpike, The-erinaceous-one, ArthurPSmith, SlowByte:  Done computational complexity (P10374) Pamputt (talk) 11:57, 19 February 2022 (UTC)