Talk:Counting problem (complexity)

Why is y less than or equal to c_r?

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

Notation

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)