Editing Unary numeral system (section)

==Complexity==
Compared to standard [[Positional notation|positional numeral systems]], the unary system is inconvenient and hence is not used in practice for large calculations. It occurs in some [[decision problem]] descriptions in [[theory of computation|theoretical computer science]] (e.g. some [[P-complete]] problems), where it is used to "artificially" decrease the run-time or space requirements of a problem. For instance, the problem of [[integer factorization]] is suspected to require more than a polynomial function of the length of the input as run-time if the input is given in [[binary numeral system|binary]], but it only needs linear runtime if the input is presented in unary.<ref>{{citation
 | last1 = Arora | first1 = Sanjeev | author-link1 = Sanjeev Arora
 | last2 = Barak | first2 = Boaz
 | year = 2007
 | chapter = The computational model&nbsp;—and why it doesn't matter
 | title = Computational Complexity: A Modern Approach
 | publisher = Cambridge University Press
 | at = §17, pp. 32–33
 | edition = January 2007 draft
 | chapter-url = http://www.cs.princeton.edu/theory/complexity/modelchap.pdf
 | access-date = May 10, 2017
 }}.</ref> However, this is potentially misleading. Using a unary input is slower for any given number, not faster; the distinction is that a binary (or larger base) input is proportional to the base 2 (or larger base) logarithm of the number while unary input is proportional to the number itself. Therefore, while the run-time and space requirement in unary looks better as function of the input size, it does not represent a more efficient solution.<ref>{{citation|title=The Nature of Computation|first1=Cristopher|last1=Moore|author1-link=Cristopher Moore|first2=Stephan|last2=Mertens|publisher=Oxford University Press|year=2011|isbn=9780199233212|page=29|url=https://books.google.com/books?id=z4zMiZyAE1kC&pg=PA29}}.</ref>

In [[computational complexity theory]], unary numbering is used to distinguish [[strongly NP-complete]] problems from problems that are [[NP-complete]] but not strongly NP-complete. A problem in which the input includes some numerical parameters is strongly NP-complete if it remains NP-complete even when the size of the input is made artificially larger by representing the parameters in unary. For such a problem, there exist hard instances for which all parameter values are at most polynomially large.<ref>{{citation
 | last1 = Garey | first1 = M. R. | author1-link = Michael R. Garey
 | last2 = Johnson | first2 = D. S. | author2-link = David S. Johnson
 | doi = 10.1145/322077.322090
 | issue = 3
 | journal = [[Journal of the ACM]]
 | mr = 478747
 | pages = 499–508
 | title = 'Strong' NP-completeness results: Motivation, examples, and implications
 | volume = 25
 | year = 1978| s2cid = 18371269 | doi-access = free
 }}.</ref>