Content deleted Content added
→Notation: new section Tags: Mobile edit Mobile web edit |
|||
Line 5:
In my understanding the symbol <math>y</math> denotes a non-negative integer that can hence be compared to <math>c_R(x)</math>, the size (that is number of elements) of the set of solutions <math>\{y\mid (x,y)\in R\}</math>. 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 <math>R</math> 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 <math>x</math>. For such <math>x</math> every pair <math>(x,n)</math> will belong to <math>\#R</math>. One way to make the number <math>c_R(x)</math> always finite is to just postulate this in the definition of <math>R</math>. Often this is achieved by making more restrictive assumptions such a that there is a function <math>f\colon \mathbb{N}\to\mathbb{N}</math> (of a certain kind, e.g. a polynomial function) such that for every input <math>x</math> there are ''only'' solutions <math>y</math> satisfying <math>(x,y)\in R</math> with bounded length <math>|y|\leq f(|x|)</math> and hence
finitely many.
== Notation ==
I think the problem needs to be stated in English, as with this unspecified notation it's basically unintelligible. [[Special:Contributions/81.2.154.16|81.2.154.16]] ([[User talk:81.2.154.16|talk]]) 20:30, 7 July 2022 (UTC)
| |||