Talk:Counting problem (complexity)

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 ${\displaystyle y}${\displaystyle y} denotes a non-negative integer that can hence be compared to ${\displaystyle c_{R}(x)}${\displaystyle c_{R}(x)}, the size (that is number of elements) of the set of solutions ${\displaystyle \{y\mid (x,y)\in R\}}${\displaystyle \{y\mid (x,y)\in R\}}. 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 ${\displaystyle R}${\displaystyle R} 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 ${\displaystyle x}${\displaystyle x}. For such ${\displaystyle x}${\displaystyle x} every pair ${\displaystyle (x,n)}${\displaystyle (x,n)} will belong to ${\displaystyle \#R}${\displaystyle \#R}. One way to make the number ${\displaystyle c_{R}(x)}${\displaystyle c_{R}(x)} always finite is to just postulate this in the definition of ${\displaystyle R}${\displaystyle R}. Often this is achieved by making more restrictive assumptions such a that there is a function ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }${\displaystyle f\colon \mathbb {N} \to \mathbb {N} } (of a certain kind, e.g. a polynomial function) such that for every input ${\displaystyle x}${\displaystyle x} there are only solutions ${\displaystyle y}${\displaystyle y} satisfying ${\displaystyle (x,y)\in R}${\displaystyle (x,y)\in R} with bounded length ${\displaystyle |y|\leq f(|x|)}${\displaystyle |y|\leq f(|x|)} and hence finitely many.

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 ]

• Stub-Class Computer science articles
• Unknown-importance Computer science articles
• WikiProject Computer science articles