计算复杂性理论
此词条暂由彩云小译翻译，翻译字数共739，未经人工整理和审校，带来阅读不便，请见谅。
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.
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 computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.[1]
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 computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.
如果一个问题的解决需要大量的资源，无论使用什么算法，那么这个问题本身就被认为是困难的。该理论通过引入计算的数学模型来研究这些问题，并量化它们的计算复杂性，即解决这些问题所需的资源量，如时间和存储量，将这种直觉形式化。复杂性的其他度量也被使用，例如通信量(用于通信复杂性) ，电路中的门数(用于电路复杂性)和处理器数(用于并行计算)。计算复杂性理论的一个作用是确定计算机能做什么和不能做什么的实际限制。P/NP问题计算复杂性研究所是7个千禧年大奖难题计算复杂性研究所之一，致力于计算复杂性研究领域。
Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically.
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. Such problems are called [[NP-intermediate problems. The graph isomorphism problem, the discrete logarithm problem and the integer factorization problem are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in P or to be NP-complete.
在 p ≠ NP 的情况下，复杂性类的图表。在这种情况下，p 和 NP 完全以外的 NP 问题的存在性是由拉德纳建立的。这类问题称为[ np 中间问题。图同构问题、离散对数问题和整数分解问题就是被认为是 np 中间问题的例子。它们是极少数几个 NP 问题中的一些，不知道是 p 或 NP 完全问题。
Computational problems
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in P, NP-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete. John Myhill's definition of linear bounded automata (Myhill 1960), Raymond Smullyan's study of rudimentary sets (1961), as well as Hisao Yamada's paper on real-time computations (1962). Somewhat earlier, Boris Trakhtenbrot (1956), a pioneer in the field from the USSR, studied another specific complexity measure. As he remembers:
图同构问题是判定两个有限图是否同构的计算问题。复杂性理论中一个尚未解决的重要问题是图的同构问题是在 p、 np 完全还是 np 中间。答案不得而知，但是人们相信这个问题至少不是 np 完全问题。线性有界自动机的定义(Myhill 1960) ，雷蒙·史慕扬对不完备集的研究(1961) ，以及 Hisao Yamada 关于实时计算的论文(1962)。更早些时候，Boris Trakhtenbrot (1956) ，苏联在这一领域的先驱，研究了另一个具体的复杂性度量。他回忆道:
Problem instances
A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing. The instance is a number (e.g., 15) and the solution is "yes" if the number is prime and "no" otherwise (in this case, 15 is not prime and the answer is "no"). Stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input.
In 1967, Manuel Blum formulated a set of axioms (now known as Blum axioms) specifying desirable properties of complexity measures on the set of computable functions and proved an important result, the so-called speed-up theorem. The field began to flourish in 1971 when the Stephen Cook and Leonid Levin proved the existence of practically relevant problems that are NP-complete. In 1972, Richard Karp took this idea a leap forward with his landmark paper, "Reducibility Among Combinatorial Problems", in which he showed that 21 diverse combinatorial and graph theoretical problems, each infamous for its computational intractability, are NP-complete.
1967年，Manuel Blum 提出了一组公理(现在称为 Blum 公理) ，在可计算函数集上指定了复杂度量的理想性质，并证明了一个重要的结果，即所谓的加速定理。这个领域在1971年开始蓬勃发展，当时史蒂芬 · 库克和莱昂尼德 · 莱文证明了存在实际上相关的 np 完全问题。1972年，理查德 · 卡普在他具有里程碑意义的论文《组合问题中的可约性》中，向我们展示了21个不同的组合和图论问题，每个问题都因其难于计算而臭名昭著，这是 np 完全问题。
To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.
In the 1980s, much work was done on the average difficulty of solving NP-complete problems—both exactly and approximately. At that time, computational complexity theory was at its height, and it was widely believed that if a problem turned out to be NP-complete, then there was little chance of being able to work with the problem in a practical situation. However, it became increasingly clear that this is not always the case, and some authors claimed that general asymptotic results are often unimportant for typical problems arising in practice.
20世纪80年代，人们在解决 np 完全问题的平均难度方面做了大量的工作。当时，计算复杂性理论正处于鼎盛时期，人们普遍认为，如果一个问题最终证明是 np 完全问题，那么在实际情况下处理这个问题的可能性就很小。然而，越来越清楚的是，情况并非总是如此，一些作者声称，对于实践中出现的典型问题，一般的渐近结果往往不重要。
Representing problem instances
When considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet (i.e., the set {0,1}), and thus the strings are bitstrings. As in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary.
Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently.
Decision problems as formal languages
Decision problems are one of the central objects of study in computational complexity theory. A decision problem is a special type of computational problem whose answer is either yes or no, or alternately either 1 or 0. A decision problem can be viewed as a formal language, where the members of the language are instances whose output is yes, and the non-members are those instances whose output is no. The objective is to decide, with the aid of an algorithm, whether a given input string is a member of the formal language under consideration. If the algorithm deciding this problem returns the answer yes, the algorithm is said to accept the input string, otherwise it is said to reject the input.
An example of a decision problem is the following. The input is an arbitrary graph. The problem consists in deciding whether the given graph is connected or not. The formal language associated with this decision problem is then the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings.
Function problems
A function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no. Notable examples include the traveling salesman problem and the integer factorization problem.
It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples (a, b, c) such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.
Measuring the size of an instance
To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or the space required, or any measure of complexity) is calculated as a function of the size of the instance. This is usually taken to be the size of the input in bits. Complexity theory is interested in how algorithms scale with an increase in the input size. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with 2n vertices compared to the time taken for a graph with n vertices?
If the input size is n, the time taken can be expressed as a function of n. Since the time taken on different inputs of the same size can be different, the worst-case time complexity T(n) is defined to be the maximum time taken over all inputs of size n. If T(n) is a polynomial in n, then the algorithm is said to be a polynomial time algorithm. Cobham's thesis argues that a problem can be solved with a feasible amount of resources if it admits a polynomial time algorithm.
Machine models and complexity measures
Turing machine
A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory.
Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others.
| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
1 = Arora | first1 = Sanjeev | authorlink1 = Sanjeev Arora
A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called randomized algorithms. A non-deterministic Turing machine is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see non-deterministic algorithm.
| last2=Barak | first2=Boaz
2 = Barak | first2 = Boaz
| title=Computational Complexity: A Modern Approach
| title = 计算复杂性: 一种现代方法
Other machine models
| url = http://www.cs.princeton.edu/theory/complexity/
Http://www.cs.princeton.edu/theory/complexity/
Many machine models different from the standard multi-tape Turing machines have been proposed in the literature, for example random access machines. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary.[2] What all these models have in common is that the machines operate deterministically.
| publisher=Cambridge University Press
剑桥大学出版社
| year=2009
2009年
However, some computational problems are easier to analyze in terms of more unusual resources. For example, a non-deterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The non-deterministic 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 non-deterministic time is a very important resource in analyzing computational problems.
| isbn=978-0-521-42426-4
| isbn = 978-0-521-42426-4
| zbl=1193.68112
1193.68112
Complexity measures
}}
}}
For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used. The time required by a deterministic Turing machine M on input x is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine M is said to operate within time f(n) if the time required by M on each input of length n is at most f(n). A decision problem A can be solved in time f(n) if there exists a Turing machine operating in time f(n) that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time f(n) on a deterministic Turing machine is then denoted by DTIME(f(n)).
| last1=Downey
1 = Downey
Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any complexity measure can be viewed as a computational resource. Complexity measures are very generally defined by the Blum complexity axioms. Other complexity measures used in complexity theory include communication complexity, circuit complexity, and decision tree complexity.
| first1=Rod
1 = Rod
| last2=Fellows
2 = Fellows
The complexity of an algorithm is often expressed using big O notation.
| first2=Michael
2 = Michael
| authorlink2=Michael Fellows
2 = Michael Fellows
Best, worst and average case complexity
| title=Parameterized complexity
参数化复杂度
| url=https://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html
Https://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html
The best, worst and average case complexity refer to three different ways of measuring the time complexity (or any other complexity measure) of different inputs of the same size. Since some inputs of size n may be faster to solve than others, we define the following complexities:
| publisher=Springer-Verlag
| publisher = Springer-Verlag
- Best-case complexity: This is the complexity of solving the problem for the best input of size n.
| location=Berlin, New York
| 地点: 柏林，纽约
- Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a probability distribution over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size n.
| year=1999
1999年
- Amortized analysis: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.
| isbn=9780387948836
9780387948836
- Worst-case complexity: This is the complexity of solving the problem for the worst input of size n.
| series=Monographs in Computer Science
系列 = 计算机科学专著
The order from cheap to costly is: Best, average (of discrete uniform distribution), amortized, worst.
}}
}}
For example, consider the deterministic sorting algorithm quicksort. This solves the problem of sorting a list of integers that is given as the input. The worst-case is when the pivot is always the largest or smallest value in the list (so the list is never divided). In this case the algorithm takes time O(n2). If we assume that all possible permutations of the input list are equally likely, the average time taken for sorting is O(n log n). The best case occurs when each pivoting divides the list in half, also needing O(n log n) time.
| last=Du
| last = Du
| first=Ding-Zhu
| 第一 = 鼎柱
Upper and lower bounds on the complexity of problems
| author2=Ko, Ker-I
| author2 = Ko，Ker-I
To classify the computation time (or similar resources, such as space consumption), it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem. The complexity of an algorithm is usually taken to be its worst-case complexity, unless specified otherwise. Analyzing a particular algorithm falls under the field of analysis of algorithms. To show an upper bound T(n) on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most T(n). However, proving lower bounds is much more difficult, since lower bounds make a statement about all possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of T(n) for a problem requires showing that no algorithm can have time complexity lower than T(n).
| title=Theory of Computational Complexity
计算复杂性理论
| publisher=John Wiley & Sons
2012年3月24日 | publisher = 约翰威立
Upper and lower bounds are usually stated using the big O notation, which hides constant factors and smaller terms. This makes the bounds independent of the specific details of the computational model used. For instance, if T(n) = 7n2 + 15n + 40, in big O notation one would write T(n) = O(n2).
| year=2000
2000年
| isbn=978-0-471-34506-0
| isbn = 978-0-471-34506-0
Complexity classes
}}
}}
Defining complexity classes
| last=Goldreich
| last = Goldreich
A complexity class is a set of problems of related complexity. Simpler complexity classes are defined by the following factors:
| first=Oded
第一个 = Oded
- The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on function problems, counting problems, optimization problems, promise problems, etc.
| authorlink=Oded Goldreich
| authorlink = Oded Goldreich
- The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on non-deterministic Turing machines, Boolean circuits, quantum Turing machines, monotone circuits, etc.
| url = http://www.wisdom.weizmann.ac.il/~oded/cc-book.html
Http://www.wisdom.weizmann.ac.il/~oded/cc-book.html
- The resource (or resources) that is being bounded and the bound: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc.
| title = Computational Complexity: A Conceptual Perspective
| title = 计算复杂性: 一个概念性的视角
| publisher = Cambridge University Press
剑桥大学出版社
Some complexity classes have complicated definitions that do not fit into this framework. Thus, a typical complexity class has a definition like the following:
| year = 2008
2008年
}}
}}
- The set of decision problems solvable by a deterministic Turing machine within time f(n). (This complexity class is known as DTIME(f(n)).)
| editor1-last=van Leeuwen
| editor1-last=van Leeuwen
But bounding the computation time above by some concrete function f(n) often yields complexity classes that depend on the chosen machine model. For instance, the language {xx | x is any binary string} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" 模板:Harv. This forms the basis for the complexity class P, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP.
| editor1-first=Jan
1-first = Jan
| editor1-link = Jan van Leeuwen
| editor1-link = Jan van Leeuwen
Important complexity classes
| title=Handbook of theoretical computer science (vol. A): algorithms and complexity
| title = 理论计算机科学手册。A)算法和复杂性
| publisher=MIT Press
| publisher = MIT Press
| isbn=978-0-444-88071-0
978-0-444-88071-0
Many important complexity classes can be defined by bounding the time or space used by the algorithm. Some important complexity classes of decision problems defined in this manner are the following:
| year=1990
1990年
}} }}| last = Papadimitriou | last = Papadimitriou
}}
}}
}}
}}
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
- ↑ "P vs NP Problem | Clay Mathematics Institute". www.claymath.org (in English).
- ↑ See Arora & Barak 2009, Chapter 1: The computational model and why it doesn't matter