本文共 5502 字，大约阅读时间需要 18 分钟。
A single "problem" is an entire set of related questions, where each question is a finite-length . For example, the problem is: given an integer written in binary, return all of the 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, as a function of the size of the instance. If an instance that is n bits long can be solved in n2 steps, then we say it has a time complexity of n2. Of course, the exact number of steps will depend on exactly what machine or language is being used. To avoid that problem, we generally use notation. If a problem has time complexity O(n2) on one typical computer, then it will also have complexity O(n2) on most other computers, so this notation allows us to generalize away from the details of a particular computer.
Much of complexity theory deals with decision problems. A is a problem where the answer is always YES/NO. For example, the problem IS-PRIME is: given an integer written in binary, return whether it is a prime number or not. A decision problem is equivalent to a language, which is a set of finite-length strings. For a given decision problem, the equivalent language is the set of all strings for which the answer is YES.
Decision problems are often considered because an arbitrary problem can always be reduced to a decision problem. For example, 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. Just do a binary search on k until you find the smallest factor of n. Then divide out that factor, and repeat until you find all the factors.
Complexity theory often makes a distinction between YES answers and NO answers. For example, the set NP is defined as the set of problems where the YES instances can be checked quickly. The set Co-NP is the set of problems where the NO instances can be checked quickly. The "Co" in the name stands for "complement". The complement of a problem is one where all the YES and NO answers are sped, such as IS-COMPOSITE for IS-PRIME.
The set is the set of decision problems that can be solved in . The question of whether P is the same set as is the most important open question in theoretical computer science. There is even a for solving it. (See and machine" style="TEXT-DECORATION: underline" href="http://www.wikipedia.com/wiki/Oracle+machine">oracles).
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 tranormed easily into some problem in X with the same answer. The definition of "easily" is different in different contexts. The most important hard set is . Set X is complete for Y if it is hard for Y, and is also a subset of Y. The most important complete set is . See the articles on those two sets for more detail on the definition of "hard" and "complete".
The following are some of the classes of problems considered in complexity theory, along with rough definitions. See for a chart showing which classes are subsets of other classes.
Solvable in polynomial time (see ) YES answers checkable in polynomial time (see ) NO answers checkable in polynomial time The hardest problems in NP The hardest problems in Co-NP Either NP-complete or harder non-decision-problem analogue to NP non-decision-problem analogue to NP-complete -P style="TEXT-DECORATION: underline" href="http://www.wikipedia.com/wiki/Sharp-P">#P Count solutions to an NP problem The hardest problems in #P Solvable efficiently on parallel computers The hardest problems in P to solve on parallel computers Solvable with polynomial memory and unlimited time The hardest problems in PSPACE Solvable with exponential time Solvable with exponential memory and unlimited time Solvable in polynomial time on a (answer is probably right) Solvable in polynomial time by randomized algorithms (answer is probably right) Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) Solvable by randomized algorithms (answer is always right, average running time is polynomial)
" rel="nofollow">Upload files
This page has been accessed 2248 times. Other namespaces :
Last edited: Sunday, June 2, 2002, 13:50
来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/10748419/viewspace-959375/，如需转载，请注明出处，否则将追究法律责任。
转载于:http://blog.itpub.net/10748419/viewspace-959375/