|
LH (complexity)
In computational complexity, the logarithmic time hierarchy (LH) is the complexity class of all computational problems solvable in a logarithmic amount of computation time on an alternating Turing machine with a bounded number of alternations. It is a particular case of a bounded alternating Turing machine hierarchy. It is equal to FO and to FO-uniform AC0. The ith level of the logarithmic time hierarchy is the set of languages recognised by alternating Turing machines in logarithmic time with random access Random access (more precisely and more generally called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of addressable elements roughly as easily and efficiently as any othe ... and i-1 alternations, beginning with an existential state. LH is the union of all levels. References Complexity classes {{Comp-sci-theory-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Complexity Theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computationa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complexity Class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other models of computation (e.g. probabilistic Turing machines, interactive proof systems, Boolean circuits, and quantum computers). The study of the relationships between complexity classes is a ma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Problem
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computational problem. A computational problem can be viewed as a set of ''instances'' or ''cases'' together with a, possibly empty, set of ''solutions'' for every instance/case. For example, in the factoring problem, the instances are the integers ''n'', and solutions are prime numbers ''p'' that are the nontrivial prime factors of ''n''. Computational problems are one of the main objects of study in theoretical computer science. The field of computational complexity theory attempts to determine the amount of resources ( computational complexity) solving a given problem will require and explain why some problems are intractable or undecidable. Computational problems belong to complexity classes that define broadly the resources (e.g. time, space/memory, e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Logarithmic Growth
In mathematics, logarithmic growth describes a phenomenon whose size or cost can be described as a logarithm function of some input. e.g. ''y'' = ''C'' log (''x''). Note that any logarithm base can be used, since one can be converted to another by multiplying by a fixed constant.. Logarithmic growth is the inverse of exponential growth and is very slow. A familiar example of logarithmic growth is a number, ''N'', in positional notation, which grows as log''b'' (''N''), where ''b'' is the base of the number system used, e.g. 10 for decimal arithmetic. In more advanced mathematics, the partial sums of the harmonic series :1+\frac+\frac+\frac+\frac+\cdots grow logarithmically. In the design of computer algorithms, logarithmic growth, and related variants, such as log-linear, or linearithmic, growth are very desirable indications of efficiency, and occur in the time complexity analysis of algorithms such as binary search. Logarithmic growth can lead to apparent pa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computation Time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Alternating Turing Machine
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981. Definitions Informal description The definition of NP uses the ''existential mode'' of computation: if ''any'' choice leads to an accepting state, then the whole computation accepts. The definition of co-NP uses the ''universal mode'' of computation: only if ''all'' choices lead to an accepting state does the whole computation accept. An alternating Turing machine (or to be more precise, the definition of acceptance for such a machine) alternates between these modes. An alternating Turing machine is a non-deterministic Turing machine whose states are divided into two sets: existential states ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Alternating Turing Machine
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981. Definitions Informal description The definition of NP uses the ''existential mode'' of computation: if ''any'' choice leads to an accepting state, then the whole computation accepts. The definition of co-NP uses the ''universal mode'' of computation: only if ''all'' choices lead to an accepting state does the whole computation accept. An alternating Turing machine (or to be more precise, the definition of acceptance for such a machine) alternates between these modes. An alternating Turing machine is a non-deterministic Turing machine whose states are divided into two sets: existential states ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
FO (complexity)
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them. Specifically, each logical system produces a set of queries expressible in it. The queries – when restricted to finite structures – correspond to the computational problems of traditional complexity theory. The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Neil Immerman
Neil Immerman (born 24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.Faculty directory: Neil Immerman Computer Science Department, , retrieved 2010-01-23. He is one of the key developers of , an approach he is currently applying to research in model checking, database theory, and computational complexity theory. Professor Immerman is an ed ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Random-access Turing Machine
In computational complexity, a field of computer science, random-access Turing machines are an extension of Turing machines used to speak about small complexity classes, especially for classes using logarithmic time, like DLOGTIME and the logarithmic hierarchy. Definition On a random-access Turing machine, there is a special '' pointer'' tape of logarithmic space accepting a binary vocabulary. The Turing machine has a special state such that when the binary number on the ''pointer'' tape is 'p', the Turing machine will write on the working tape the ''p''th symbol of the input. The pointer tape facility lets the Turing machine read any letter of the input without taking time to move over the entire input. This is mandatory for complexity classes using less than linear time. References * Neil Immerman ''Descriptive Complexity ''Descriptive Complexity'' is a book in mathematical logic and computational complexity theory by Neil Immerman. It concerns descriptive complexity t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Existential State
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. The concept of an ATM was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981. Definitions Informal description The definition of NP uses the ''existential mode'' of computation: if ''any'' choice leads to an accepting state, then the whole computation accepts. The definition of co-NP uses the ''universal mode'' of computation: only if ''all'' choices lead to an accepting state does the whole computation accept. An alternating Turing machine (or to be more precise, the definition of acceptance for such a machine) alternates between these modes. An alternating Turing machine is a non-deterministic Turing machine whose states are divided into two sets: existential states ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
