Talk:Counting problem (complexity)
![]() | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
Why is y less than or equal to c_r?
edity, to my understanding, isn't necessarily a number, so what's the meaning of the inequality? I think it's supposed to be y is a subset of the set defined in the cardinality of c_r..
In my understanding the symbol denotes a non-negative integer that can hence be compared to , the size (that is number of elements) of the set of solutions . I believe one needs to be a bit more careful in phrasing the definition, because a priori there is no bound on the number of solutions since in general is a binary relation between infinite sets (e.g. all strings over a finite (usually two-element) alphabet). Of course one may allow infinitely many solution for certain inputs . For such every pair will belong to . One way to make the number always finite is to just postulate this in the definition of . Often this is achieved by making more restrictive assumptions such a that there is a function (of a certain kind, e.g. a polynomial function) such that for every input there are only solutions satisfying with bounded length and hence finitely many.
Notation
editI think the problem needs to be stated in English, as with this unspecified notation it's basically unintelligible. 81.2.154.16 (talk) 20:30, 7 July 2022 (UTC)