CC (complexity)

In computational complexity theory, CC is the complexity class containing decision problems which can be solved by comparator circuits of polynomial size. Comparator circuits are sorting networks in which each comparator gate is directed, each wire is initialized with an input variable, its negation, or a constant, one of the wires is distinguished as the output wire; the most important problem, complete for CC is a decision variant of the stable marriage problem. A comparator circuit is a network of gates; each comparator gate, a directed edge connecting two wires, takes its two inputs and outputs them in sorted order. The input to any wire can be its negation, or a constant. One of the wires is designated as the output wire; the function computed by the circuit is evaluated by initializing the wires according to the input variables, executing the comparator gates in order, outputting the value carried by the output wire. The comparator circuit value problem is the problem of evaluating a comparator circuit given an encoding of the circuit and the input to the circuit.

The complexity class CC is defined as the class of problems logspace reducible to CCVP. An equivalent definition is the class of problems AC0 reducible to CCVP; as an example, a sorting network can be used to compute majority by designating the middle wire as an output wire: If the middle wire is designated as output, the wires are annotated with 16 different input variables the resulting comparator circuit computes majority. Since there are sorting networks which can be constructed in AC0, this shows that the majority function is in CC. A problem in CC is CC-complete if every problem in CC can be reduced to it using a logspace reduction; the comparator circuit value problem is CC-complete. In the stable marriage problem, there is an equal number of women; each person ranks all members of the opposite sex. A matching between men and women is stable if there are no unpaired man and woman who prefer each other over their current partners. A stable matching always exists. Among the stable matchings, there is one in which each woman gets the best man that she gets in any stable matching.

The decision version of the stable matching problem is, given the rankings of all men and women, whether a given man and a given woman are matched in the woman-optimal stable matching. Although the classical Gale–Shapley algorithm cannot be implemented as a comparator circuit, Subramanian came up with a different algorithm showing that the problem is in CC; the problem is CC-complete. Another problem, CC-complete is lexicographically-first maximal matching. In this problem, we are given a bipartite graph with an order on the vertices, an edge; the lexicographically-first maximal matching is obtained by successively matching vertices from the first bipartition to the minimal available vertices from the second bipartition. The problem asks. Scott Aaronson showed. In this problem, we are given a starting number of pebbles and a description of a program which may contain only two types of instructions: combine two piles of sizes y and z to get a new pile of size y + z, or split a pile of size y into piles of size ⌈ y / 2 ⌉ and ⌊ y / 2 ⌋.

The problem is to decide whether any pebbles are present in a particular pile after executing the program. He used this to show that the problem of deciding whether any balls reach a designated sink vertex in a Digi-Comp II-like device is CC-complete; the comparator circuit evaluation problem can be solved in polynomial time, so CC is contained in P. On the other hand, comparator circuits can solve directed reachability, so CC contains NL. There is a relativized world in which CC and NC are incomparable, so both containments are strict. Complexity Zoo: CC

Computational complexity theory

Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, 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 used, such as the amount of communication, the number of gates in a circuit and the number of processors. 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.

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 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 kind of problems can, in principle, be solved algorithmically. 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, 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 and the solution is "yes" if the number is prime and "no" otherwise. Stated another way, the instance is a particular input to the problem, the solution is the output corresponding to the given input. 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.

When considering computational problems, a problem instance is a string over an alphabet. The alphabet is taken to be the binary alphabet, 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, graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary. Though some proofs of complexity-theoretic theorems 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 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, 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; the formal language associated with this decision problem is 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. A function problem is a computational problem where a single output 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 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 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 such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving