Jump to content

Talk:Counting problem (complexity)

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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]