Talk:Counting problem (complexity)

Latest comment: 2 years ago by 81.2.154.16 in topic Notation

Why is y less than or equal to c_r?

edit

y, 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

edit

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