Information about Computational Complexity Theory
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g., execution time), and the inherent difficulty in providing efficient algorithms for specific computational problems.
A typical question of the theory is, "As the size of the input to an algorithm increases, how do the running time and memory requirements of the algorithm change and what are the implications and ramifications of that change?" In other words, the theory, among other things, investigates the scalability of computational problems and algorithms. In particular, the theory places practical limits on what computers can accomplish.
An important aspect of the theory is to categorize computational problems and algorithms into complexity classes. The most important open question of complexity theory is whether the complexity class P is the same as the complexity class NP, or is merely a subset as is generally believed. Shortly after the question was first posed, it was realised that many important industry problems in the field of operations research are of an NP subclass called NP-complete. NP-complete problems have the property that solutions to these problems are quick to check, yet the current methods to find solutions are not "efficiently scalable" (as described more formally below). More importantly, if the NP class is larger than P, then no efficiently scalable solutions exist for these problems.
The openness of the P-NP problem prompts and justifies various research areas in the computational complexity theory, such as identification of efficiently solvable special cases of common computational problems, study of the computational complexty of finding approximate or heuristic solutions, as well as research into the hierarchies of complexity classes.
A single "problem" is a complete set of related questions, where each question is a finite-length string. For example, the problem FACTORIZE is: given an integer written in binary, return all of the prime factors of that number. A particular question is called an instance. For example, "give the factors of the number 15" is one instance of the FACTORIZE problem.
The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm. To understand this intuitively, consider the example of an instance that is n bits long that can be solved in n² steps. In this example we say the problem has a time complexity of n². Of course, the exact number of steps will depend on exactly what machine or language is being used. To avoid that problem, the Big O notation is generally used (sometimes described as the "order" of the calculation, as in "on the order of"). If a problem has time complexity O(n²) on one typical computer, then it will also have complexity O(n²) on most other computers, so this notation allows us to generalize away from the details of a particular computer.
Example: Mowing grass has linear time complexity because it takes double the time to mow double the area. However, looking up something in a dictionary has only logarithmic time complexity because a double sized dictionary only has to be opened one time more (i.e. exactly in the middle, then the problem size is reduced by half).
The space complexity of a problem is a related concept, that measures the amount of space, or memory required by the algorithm. An informal analogy would be the amount of scratch paper needed while working out a problem with pen and paper. Space complexity is also measured with Big O notation.
A different measure of problem complexity, which is useful in some cases, is circuit complexity. This is a measure of the size of a boolean circuit needed to compute the answer to a problem, in terms of the number of logic gates required to build the circuit. Such a measure is useful, for example, when designing hardware microchips to compute the function instead of software.
For example, a well known decision problem IS-PRIME returns a yes answer when a given input is a prime and a no otherwise, while the problem IS-COMPOSITE determines whether a given integer is not a prime number (i.e. a composite number). When IS-PRIME returns a yes, IS-COMPOSITE returns a no, and vice versa. So the IS-COMPOSITE is a complement of IS-PRIME, and similarly IS-PRIME is a complement of IS-COMPOSITE.
Decision problems are often considered because an arbitrary problem can always be reduced to some decision problem. For instance, the problem HAS-FACTOR is: given integers n and k written in binary, return whether n has any prime factors less than k. If we can solve HAS-FACTOR with a certain amount of resources, then we can use that solution to solve FACTORIZE without much more resources. This is accomplished by doing a binary search on k until the smallest factor of n is found, then dividing out that factor and repeating until all the factors are found.
An important result in complexity theory is the fact that no matter how hard a problem can get (i.e. how much time and space resources it requires), there will always be even harder problems. For time complexity, this is proven by the time hierarchy theorem. A similar space hierarchy theorem can also be derived.
Perhaps the most well-studied computational resources are deterministic time (DTIME) and deterministic space (DSPACE). These resources represent the amount of computation time and memory space needed on a deterministic computer, like the computers that actually exist. These resources are of great practical interest, and are well-studied.
Some computational problems are easier to analyze in terms of more unusual resources. For example, a nondeterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The nondeterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that nondeterministic time is a very important resource in analyzing computational problems.
Many more unusual computational resources have been used in complexity theory. Technically, any complexity measure can be viewed as a computational resource, and complexity measures are very broadly defined by the Blum complexity axioms.
The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to an intuitive idea of the problems which can be effectively solved in the worst cases.[1]
The complexity class NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. This class contains many problems that people would like to be able to solve effectively, including the Boolean satisfiability problem, the Hamiltonian path problem and the vertex cover problem. All the problems in this class have the property that their solutions can be checked efficiently.<ref name="Sipser2006" />
Many complexity classes can be characterized in terms of the mathematical logic needed to express them – this field is called descriptive complexity.
The question of whether NP is the same set as P (that is whether problems that can be solved in non-deterministic polynomial time can be solved in deterministic polynomial time) is one of the most important open questions in theoretical computer science due to the wide implications a solution would present.[1] If it were true, many important problems would be shown to have "efficient" solutions. These include various types of integer programming in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems efficiently using computers.[2][3] The P=NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute the solution of which is a US$1,000,000 prize for the first person to provide a solution.[4]
Questions like this motivate the concepts of hard and complete. A set of problems X is hard for a set of problems Y if every problem in Y can be transformed "easily" into some problem in X that produces the same solution. The definition of "easily" is different in different contexts. In the particular case of P versus NP, the relevant hard set is NP-hard – a set of problems, that are not necessarily in NP themselves, but to which any NP problem can be reduced in polynomial time.
Set X is complete for Y if it is hard for Y, and is also a subset of Y. Thus, the set of NP-complete problems contains the most "difficult" problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem of P = NP remains unsolved, being able to reduce a problem to a known NP-complete problem would indicate that there is no known polynomial-time solution for it. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.[1]
Another open question related to the P = NP problem is whether there exist problems that are in NP, but not in P, that are not NP-complete. In other words problems that have to be solved in non-deterministic polynomial time, but cannot be reduced to in polynomial time from other non-deterministic polynomial time problems. One such problem, that is known to be NP but not known to be NP-complete, is the graph isomorphism problem – a problem that tries to decide whether two graphs are isomorphic (i.e. share the same properties). It has been shown that if P ≠ NP then such problems exist.[6]
Problems that are solvable in theory, but cannot be solved in practice, are called intractable. Naive complexity theory assumes problems that lack polynomial-time solutions are intractable for more than the smallest inputs. Problems that are known to be intractable in this sense include those that are EXPTIME-complete. If NP is not the same as P, then the NP-complete problems are also intractable in this sense. What this means "in practice" is open to debate.
To see why exponential-time solutions might be unusable in practice, consider a problem that requires 2n operations to solve (n is the size of the input). For a relatively small input size of n=100, and assuming a computer that can perform 1012 operations per second, a solution would take about 4×1010 years, much longer than the current age of the universe. On the other hand, a problem that requires n15 operations would be in P, yet a solution would also take about 4×1010 years for n=100. And a problem that required 20.0000001*n operations would not be in P, but would be solvable for quite large cases.
Finally, saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases.
..... Click the link for more information.
A typical question of the theory is, "As the size of the input to an algorithm increases, how do the running time and memory requirements of the algorithm change and what are the implications and ramifications of that change?" In other words, the theory, among other things, investigates the scalability of computational problems and algorithms. In particular, the theory places practical limits on what computers can accomplish.
An important aspect of the theory is to categorize computational problems and algorithms into complexity classes. The most important open question of complexity theory is whether the complexity class P is the same as the complexity class NP, or is merely a subset as is generally believed. Shortly after the question was first posed, it was realised that many important industry problems in the field of operations research are of an NP subclass called NP-complete. NP-complete problems have the property that solutions to these problems are quick to check, yet the current methods to find solutions are not "efficiently scalable" (as described more formally below). More importantly, if the NP class is larger than P, then no efficiently scalable solutions exist for these problems.
The openness of the P-NP problem prompts and justifies various research areas in the computational complexity theory, such as identification of efficiently solvable special cases of common computational problems, study of the computational complexty of finding approximate or heuristic solutions, as well as research into the hierarchies of complexity classes.
Overview
Complexity theory deals with the relative computational difficulty of computable functions. This differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.A single "problem" is a complete set of related questions, where each question is a finite-length string. For example, the problem FACTORIZE is: given an integer written in binary, return all of the prime factors of that number. A particular question is called an instance. For example, "give the factors of the number 15" is one instance of the FACTORIZE problem.
The time complexity of a problem is the number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm. To understand this intuitively, consider the example of an instance that is n bits long that can be solved in n² steps. In this example we say the problem has a time complexity of n². Of course, the exact number of steps will depend on exactly what machine or language is being used. To avoid that problem, the Big O notation is generally used (sometimes described as the "order" of the calculation, as in "on the order of"). If a problem has time complexity O(n²) on one typical computer, then it will also have complexity O(n²) on most other computers, so this notation allows us to generalize away from the details of a particular computer.
Example: Mowing grass has linear time complexity because it takes double the time to mow double the area. However, looking up something in a dictionary has only logarithmic time complexity because a double sized dictionary only has to be opened one time more (i.e. exactly in the middle, then the problem size is reduced by half).
The space complexity of a problem is a related concept, that measures the amount of space, or memory required by the algorithm. An informal analogy would be the amount of scratch paper needed while working out a problem with pen and paper. Space complexity is also measured with Big O notation.
A different measure of problem complexity, which is useful in some cases, is circuit complexity. This is a measure of the size of a boolean circuit needed to compute the answer to a problem, in terms of the number of logic gates required to build the circuit. Such a measure is useful, for example, when designing hardware microchips to compute the function instead of software.
Decision problems
Much of complexity theory deals with decision problems. A decision problem is a problem where the answer is always yes or no. Complexity theory distinguishes between problems verifying yes and problems verifying no answers. A problem that reverses the yes and no answers of another problem is called a complement of that problem.For example, a well known decision problem IS-PRIME returns a yes answer when a given input is a prime and a no otherwise, while the problem IS-COMPOSITE determines whether a given integer is not a prime number (i.e. a composite number). When IS-PRIME returns a yes, IS-COMPOSITE returns a no, and vice versa. So the IS-COMPOSITE is a complement of IS-PRIME, and similarly IS-PRIME is a complement of IS-COMPOSITE.
Decision problems are often considered because an arbitrary problem can always be reduced to some decision problem. For instance, the problem HAS-FACTOR is: given integers n and k written in binary, return whether n has any prime factors less than k. If we can solve HAS-FACTOR with a certain amount of resources, then we can use that solution to solve FACTORIZE without much more resources. This is accomplished by doing a binary search on k until the smallest factor of n is found, then dividing out that factor and repeating until all the factors are found.
An important result in complexity theory is the fact that no matter how hard a problem can get (i.e. how much time and space resources it requires), there will always be even harder problems. For time complexity, this is proven by the time hierarchy theorem. A similar space hierarchy theorem can also be derived.
Computational resources
Complexity theory analyzes the difficulty of computational problems in terms of many different computational resources. The same problem can be explained in terms of the necessary amounts of many different computational resources, including time, space, randomness, alternation, and other less-intuitive measures. A complexity class is the set of all of the computational problems which can be solved using a certain amount of a certain computational resource.Perhaps the most well-studied computational resources are deterministic time (DTIME) and deterministic space (DSPACE). These resources represent the amount of computation time and memory space needed on a deterministic computer, like the computers that actually exist. These resources are of great practical interest, and are well-studied.
Some computational problems are easier to analyze in terms of more unusual resources. For example, a nondeterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The nondeterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that nondeterministic time is a very important resource in analyzing computational problems.
Many more unusual computational resources have been used in complexity theory. Technically, any complexity measure can be viewed as a computational resource, and complexity measures are very broadly defined by the Blum complexity axioms.
Complexity classes
A complexity class is the set of all of the computational problems which can be solved using a certain amount of a certain computational resource.The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to an intuitive idea of the problems which can be effectively solved in the worst cases.[1]
The complexity class NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. This class contains many problems that people would like to be able to solve effectively, including the Boolean satisfiability problem, the Hamiltonian path problem and the vertex cover problem. All the problems in this class have the property that their solutions can be checked efficiently.<ref name="Sipser2006" />
Many complexity classes can be characterized in terms of the mathematical logic needed to express them – this field is called descriptive complexity.
Open questions
The P = NP question
- See also:
The question of whether NP is the same set as P (that is whether problems that can be solved in non-deterministic polynomial time can be solved in deterministic polynomial time) is one of the most important open questions in theoretical computer science due to the wide implications a solution would present.[1] If it were true, many important problems would be shown to have "efficient" solutions. These include various types of integer programming in operations research, many problems in logistics, protein structure prediction in biology, and the ability to find formal proofs of pure mathematics theorems efficiently using computers.[2][3] The P=NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute the solution of which is a US$1,000,000 prize for the first person to provide a solution.[4]
Questions like this motivate the concepts of hard and complete. A set of problems X is hard for a set of problems Y if every problem in Y can be transformed "easily" into some problem in X that produces the same solution. The definition of "easily" is different in different contexts. In the particular case of P versus NP, the relevant hard set is NP-hard – a set of problems, that are not necessarily in NP themselves, but to which any NP problem can be reduced in polynomial time.
Set X is complete for Y if it is hard for Y, and is also a subset of Y. Thus, the set of NP-complete problems contains the most "difficult" problems in NP, in the sense that they are the ones most likely not to be in P. Because the problem of P = NP remains unsolved, being able to reduce a problem to a known NP-complete problem would indicate that there is no known polynomial-time solution for it. Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP.[1]
Incomplete problems in NP
)
Diagram of complexity classes provided that P ≠ NP. The existence of problems in NP outside both P and NP-complete in this case was established by Ladner.[5]
NP = co-NP
Where co-NP is the set containing the complement problems (i.e. problems with the yes/no answers reversed) of NP problems. It is believed that the two classes are not equal, however it has not yet been proven. It has been shown that if these two complexity classes are not equal, then it follows that no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP.[6]Intractability
- See also: Combinatorial explosion
Problems that are solvable in theory, but cannot be solved in practice, are called intractable. Naive complexity theory assumes problems that lack polynomial-time solutions are intractable for more than the smallest inputs. Problems that are known to be intractable in this sense include those that are EXPTIME-complete. If NP is not the same as P, then the NP-complete problems are also intractable in this sense. What this means "in practice" is open to debate.
To see why exponential-time solutions might be unusable in practice, consider a problem that requires 2n operations to solve (n is the size of the input). For a relatively small input size of n=100, and assuming a computer that can perform 1012 operations per second, a solution would take about 4×1010 years, much longer than the current age of the universe. On the other hand, a problem that requires n15 operations would be in P, yet a solution would also take about 4×1010 years for n=100. And a problem that required 20.0000001*n operations would not be in P, but would be solvable for quite large cases.
Finally, saying that a problem is not in P does not imply that all large cases of the problem are hard or even that most of them are. For example the decision problem in Presburger arithmetic has been shown not to be in P, yet algorithms have been written that solve the problem in reasonable times in most cases.
Researchers that have laid the foundations of the computational complexity theory
- Manuel Blum, who developed an axiomatic complexity theory based on his Blum axioms
- Allan Borodin
- Stephen Cook
- Michael R. Garey
- Oded Goldreich
- Juris Hartmanis
- David S. Johnson
- Richard Karp
- Donald Knuth
- Leonid Levin
- Christos H. Papadimitriou
- Alexander Razborov
- Richard Stearns
- Leslie Valiant
- Andrew Yao
See also
- Complexity
- List of important publications in computational complexity theory
- List of open problems in computational complexity theory
- List of computability and complexity topics
- Game complexity
- The Complexity of Songs
- Run-time analysis
References
- L. Fortnow, Steve Homer (2002/2003). A Short History of Computational Complexity. In D. van Dalen, J. Dawson, and A. Kanamori, editors, The History of Mathematical Logic. North-Holland, Amsterdam.
- Jan van Leeuwen, ed. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, 1990. ISBN 978-0-444-88071-0 (Volume A). QA 76.H279 1990. Huge compendium of information, 1000s of references in the various articles.
1. ^ Sipser, Michael (2006). "Time Complexity", Introduction to the Theory of Computation, 2nd edition, USA: Thomson Course Technology. ISBN 0534950973.
2. ^ Berger, Bonnie A.; Leighton, Terrance (1998). "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete". Journal of Computational Biology 5: p27-40. PubMed.
3. ^ Cook, Stephen (April 2000). "The P versus NP Problem". Retrieved on 2006-10-18.
4. ^ Jaffe, Arthur M. (2006). "The Millennium Grand Challenge in Mathematics". Notices of the AMS 53 (6). Retrieved on 2006-10-18.
5. ^ Ladner, Richard E. (1975). "On the structure of polynomial time reducibility" (PDF). Journal of the ACM (JACM) 22: 151–171. DOI:10.1145/321864.321877.
6. ^ Du, Ding-Zhu; Ko, Ker-I (2000). Theory of Computational Complexity. John Wiley & Sons. ISBN 978-0-471-34506-0.
2. ^ Berger, Bonnie A.; Leighton, Terrance (1998). "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete". Journal of Computational Biology 5: p27-40. PubMed.
3. ^ Cook, Stephen (April 2000). "The P versus NP Problem". Retrieved on 2006-10-18.
4. ^ Jaffe, Arthur M. (2006). "The Millennium Grand Challenge in Mathematics". Notices of the AMS 53 (6). Retrieved on 2006-10-18.
5. ^ Ladner, Richard E. (1975). "On the structure of polynomial time reducibility" (PDF). Journal of the ACM (JACM) 22: 151–171. DOI:10.1145/321864.321877.
6. ^ Du, Ding-Zhu; Ko, Ker-I (2000). Theory of Computational Complexity. John Wiley & Sons. ISBN 978-0-471-34506-0.
External links
- – a Wiki on complexity classes.
- Free (at least for now) book on computational complexity
Important complexity classes (more) |
|---|
| P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH |
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems.
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
The simplest computational resources are computation time, the number of steps necessary to solve a problem, and
..... Click the link for more information.
The simplest computational resources are computation time, the number of steps necessary to solve a problem, and
..... Click the link for more information.
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will proceed through a well-defined series of successive states, eventually terminating in an
..... Click the link for more information.
..... Click the link for more information.
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
..... Click the link for more information.
In theoretical computer science, a computational problem is a mathematical object representing a question that computers might want to solve. For example, "given any number x, determine whether x is prime" is a computational problem.
..... Click the link for more information.
..... Click the link for more information.
In telecommunications and software engineering, scalability is a desirable property of a system, a network, or a process, which indicates its ability to either handle growing amounts of work in a graceful manner, or to be readily enlarged.
..... Click the link for more information.
..... Click the link for more information.
computer is a machine which manipulates data according to a list of instructions.
Computers take numerous physical forms. The first devices that resemble modern computers date to the mid-20th century (around 1940 - 1941), although the computer concept and various machines
..... Click the link for more information.
Computers take numerous physical forms. The first devices that resemble modern computers date to the mid-20th century (around 1940 - 1941), although the computer concept and various machines
..... Click the link for more information.
In computational complexity theory, a complexity class is a set of problems of related complexity. A typical complexity class has a definition of the form:
..... Click the link for more information.
- the set of problems that can be solved by abstract machine M using O(f(n)) of resource R (n
..... Click the link for more information.
In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, NP ("Non-deterministic Polynomial time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine.
..... Click the link for more information.
..... Click the link for more information.
Operations Research or Operational Research (OR) is an interdisciplinary branch of mathematics which uses methods like mathematical modeling, statistics, and algorithms to arrive at optimal or good decisions in complex problems which are concerned with optimizing the maxima
..... Click the link for more information.
..... Click the link for more information.
In complexity theory, the NP-complete problems are the most difficult problems in NP ("non-deterministic polynomial time") in the sense that they are the smallest subclass of NP that could conceivably remain outside of P, the class of deterministic polynomial-time problems.
..... Click the link for more information.
..... Click the link for more information.
Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. They make precise the intuitive notion of algorithm. Computable functions can be used to discuss computability without referring to any concrete model of computation
..... Click the link for more information.
..... Click the link for more information.
computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation.
Computability theory differs from the related discipline of computational complexity theory, which deals with the
..... Click the link for more information.
Computability theory differs from the related discipline of computational complexity theory, which deals with the
..... Click the link for more information.
string is an ordered sequence of symbols. These symbols are chosen from a predetermined set.
In programming, when stored in memory each symbol is represented using a numeric value.
..... Click the link for more information.
In programming, when stored in memory each symbol is represented using a numeric value.
..... Click the link for more information.
integer factorization is the process of breaking down a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer.
..... Click the link for more information.
..... Click the link for more information.
binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2.
..... Click the link for more information.
..... Click the link for more information.
In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. An infinitude of prime numbers exists, as demonstrated by Euclid in about 300 BC.
..... Click the link for more information.
..... Click the link for more information.
problem size. The problem size measures the size, in some sense, of the input to the algorithm. The problem size has to be cleanly defined before an algorithm analysis can be attempted.
..... Click the link for more information.
..... Click the link for more information.
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will proceed through a well-defined series of successive states, eventually terminating in an
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithm's usage of computational resources (usually running time or memory).
..... Click the link for more information.
..... Click the link for more information.
A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value by selecting the median element in a list, comparing its value to the target value, and
..... Click the link for more information.
..... Click the link for more information.
Edison cylinder phonograph ca. 1899. The Phonograph cylinder is a storage medium. The phonograph may or may not be considered a storage device.]] A data storage device is a device for recording (storing) information (data).
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithm's usage of computational resources (usually running time or memory).
..... Click the link for more information.
..... Click the link for more information.
Circuit complexity is a topic in computational complexity theory, a branch of theoretical computer science which classifies boolean functions according to the amount of computational resources needed to compute them.
..... Click the link for more information.
..... Click the link for more information.
..... Click the link for more information.
A logic gate performs a logical operation on one or more logic inputs and produces a single logic output. The logic normally performed is Boolean logic and is most commonly found in digital circuits.
..... Click the link for more information.
..... Click the link for more information.
integrated circuit (also known as IC, microcircuit, microchip, silicon chip, or chip) is a miniaturized electronic circuit (consisting mainly of semiconductor devices, as well as passive components) that has been manufactured in the surface of a
..... Click the link for more information.
..... Click the link for more information.
Computer software is a general term used to describe a collection of computer programs, procedures and documentation that perform some task on a computer system. [1]
..... Click the link for more information.
..... Click the link for more information.
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem.
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
