Proper complexity function
- Proper complexity function
A proper complexity function is a function "f" mapping a natural number to a natural number 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")) spaces, and output "s" "f"("n") consecutive blanks.
If "f" and "g" are two proper complexity functions, then "f" + "g", "fg", and 2"f", are also proper complexity functions.
Similar notions include honest function, space-constructible function, and time-constructible function.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Function point — A function point is a unit of measurement to express the amount of business functionality an information system provides to a user. Function points are the units of measure used by the IFPUG Functional Size Measurement Method. The IFPUG FSM… … Wikipedia
Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… … Wikipedia
Complexity index — Besides complexity intended as a difficulty to compute a function (see computational complexity), in modern computer science and in statistics another complexity index of a function stands for denoting its information content, in turn affecting… … Wikipedia
complexity — /keuhm plek si tee/, n., pl. complexities for 2. 1. the state or quality of being complex; intricacy: the complexity of urban life. 2. something complex: the complexities of foreign policy. [1715 25; COMPLEX + ITY] * * * ▪ scientific theory… … Universalium
One-way compression function — In cryptography, a one way compression function is a function that transforms two fixed length inputs to an output of the same size as one of the inputs. The transformation is one way , meaning that it is difficult given a particular output to… … Wikipedia
Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… … Wikipedia
Model of Hierarchical Complexity — The model of hierarchical complexity is a framework for scoring how complex a behavior is. It quantifies the order of hierarchical complexity of a task based on mathematical principles of how the information is organized and of information… … Wikipedia
NC (complexity) — Unsolved problems in computer science Is NC = P ? In complexity theory, the class NC (for Nick s Class ) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In… … Wikipedia
Model of hierarchical complexity — The model of hierarchical complexity, is a framework for scoring how complex a behavior is. It quantifies the order of hierarchical complexity of a task based on mathematical principles of how the information is organized and of information… … Wikipedia
Primitive recursive function — The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the recursive functions (recursive functions are also known as computable functions). The term was coined by… … Wikipedia
