A proper complexity function is a function f mapping natural numbers to natural numbers such that:

  • f is nondecreasing;
  • there exists a k-string Turing machine M such that on any input of length n, M halts after O(n + f(n)) steps, uses O(f(n)) space, and outputs f(n) consecutive blanks.

If f and g are two proper complexity functions, then f + g, fg, and 2f are also proper complexity functions.

Similar notions include honest functions, space-constructible functions, and time-constructible functions.

References

edit

Myashnikov, Alexei; Shpilrain, Vladimir; Ushakov, Vladimir (2008). Group-based Cryptography. Birkhauser. p. 28. ISBN 978-3-7643-8826-3.

📚 Artikel Terkait di Wikipedia

Complexity class

There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other

Proper noun

romanization for Mandarin Chinese, capitalization is used to mark proper names, with some complexities because of different Chinese classifications of nominal types

Function point

Early and easy function points – Adjusts for problem and data complexity with two questions that yield a somewhat subjective complexity measurement; simplifies

Primitive recursive function

time complexity is bounded above by a primitive recursive function of the input size. It is hence not particularly easy to devise a computable function that

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource

One-way function

computational complexity theory, specifically the theory of polynomial time problems. This has nothing to do with whether the function is one-to-one;

Class (set theory)

are proper classes in many formal systems. In Quine's set-theoretical writing, the phrase "ultimate class" is often used instead of the phrase "proper class"

NC (complexity)

{\displaystyle {\mathsf {NC}}} hierarchy proper? More unsolved problems in computer science One major open question in complexity theory is whether or not every