Talk:Computational complexity theory: Difference between revisions

Revision as of 04:56, 22 May 2018

Revision as of 05:00, 22 May 2018

Line 549:

Also the [https://plato.stanford.edu/entries/computational-complexity/#BasCon Stanford Encyclopedia of Philosophy] says

{{quote|For each problem X, it is also assumed that an appropriate notion of problem size is defined for its instances. Formally, this is a function |⋅|:X→N chosen so that the efficiency of a decision algorithm for X will varying uniformly in |x|. As we have seen, if X⊆N, it is standard to take |n| =log2(n) i.e. the number of digits (or length) of the binary numeral ┌n┐ representing n}}

These are two citations for the original statement.