CC (complexity)

Last updated

In computational complexity theory, CC (Comparator Circuits) is the complexity class containing decision problems which can be solved by comparator circuits of polynomial size.

Contents

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, and one of the wires is distinguished as the output wire.

The most important problem which is complete for CC is a decision variant of the stable marriage problem.

Definition

A single comparator gate. Comparator gate in a comparator circuit.png
A single comparator gate.

A comparator circuit is a network of wires and gates. Each comparator gate, which is a directed edge connecting two wires, takes its two inputs and outputs them in sorted order (the larger value ending up in the wire the edge is pointing to). The input to any wire can be either a variable, 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, and outputting the value carried by the output wire.

The comparator circuit value problem (CCVP) 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. [1] An equivalent definition [2] 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:

BitonicSort1.svg

If the middle wire is designated as output, and the wires are annotated with 16 different input variables, then 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.

CC-complete problems

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 (CCVP) is CC-complete.

In the stable marriage problem, there is an equal number of men and 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 ever gets in any stable matching; this is known as the woman-optimal 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 [3] came up with a different algorithm showing that the problem is in CC. The problem is also CC-complete.

Another problem which is CC-complete is lexicographically-first maximal matching. [3] In this problem, we are given a bipartite graph with an order on the vertices, and 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 whether the given edge belongs to this matching.

Scott Aaronson showed that the pebbles model is CC-complete. [4] In this problem, we are given a starting number of pebbles (encoded in unary) and a description of a program which may contain only two types of instructions: combine two piles of sizes and to get a new pile of size , or split a pile of size into piles of size and . 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 also CC-complete.

Containments

The comparator circuit evaluation problem can be solved in polynomial time, and so CC is contained in P ("circuit universality"). On the other hand, comparator circuits can solve directed reachability, [3] and so CC contains NL . There is a relativized world in which CC and NC are incomparable, [2] and so both containments are strict.

Related Research Articles

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

In computational complexity theory, the class NC is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem with input size n is in NC if there exist constants c and k such that it can be solved in time O(logc n) using O(nk) parallel processors. Stephen Cook coined the name "Nick's class" after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size.

The #P-complete problems form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties:

In computational complexity theory, a decision problem is P-complete if it is in P and every problem in P can be reduced to it by an appropriate reduction.

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

<span class="mw-page-title-main">Independent set (graph theory)</span> Unrelated vertices in graphs

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.

<span class="mw-page-title-main">Sorting network</span>

In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform sorting on fixed numbers of values, in which case they are called sorting networks.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes , and for sparse random graphs it runs in time with high probability.

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

<span class="mw-page-title-main">Boolean circuit</span> Model of computation

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length.

<span class="mw-page-title-main">Circuit complexity</span> Model of computational complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits .

The #P-completeness of 01-permanent, sometimes known as Valiant's theorem, is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory. In a 1979 scholarly paper, Leslie Valiant proved that the computational problem of computing the permanent of a matrix is #P-hard, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even #P-complete, because it corresponds to the #P problem of counting the number of permutation matrices one can get by changing ones into zeroes.

In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematical model for digital logic circuits. Circuits are defined by the gates they contain and the values the gates can produce. For example, the values in a Boolean circuit are boolean values, and the circuit includes conjunction, disjunction, and negation gates. The values in an integer circuit are sets of integers and the gates compute set union, set intersection, and set complement, as well as the arithmetic operations addition and multiplication.

In theoretical computer science, the circuit satisfiability problem is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true. In other words, it asks whether the inputs to a given Boolean circuit can be consistently set to 1 or 0 such that the circuit outputs 1. If that is the case, the circuit is called satisfiable. Otherwise, the circuit is called unsatisfiable. In the figure to the right, the left circuit can be satisfied by setting both inputs to be 1, but the right circuit is unsatisfiable.

<span class="mw-page-title-main">Half graph</span>

In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bipartite graph on the same vertices. The name was given to these graphs by Paul Erdős and András Hajnal.

In computer science, an enumeration algorithm is an algorithm that enumerates the answers to a computational problem. Formally, such an algorithm applies to problems that take an input and produce a list of solutions, similarly to function problems. For each input, the enumeration algorithm must produce the list of all solutions, without duplicates, and then halt. The performance of an enumeration algorithm is measured in terms of the time required to produce the solutions, either in terms of the total time required to produce all solutions, or in terms of the maximal delay between two consecutive solutions and in terms of a preprocessing time, counted as the time before outputting the first solution. This complexity can be expressed in terms of the size of the input, the size of each individual output, or the total size of the set of all outputs, similarly to what is done with output-sensitive algorithms.

References

  1. ↑ E. W. Mayr; A. Subramanian (1992). "The complexity of circuit value and network stability". Journal of Computer and System Sciences. 44 (2): 302–323. doi: 10.1016/0022-0000(92)90024-d .
  2. 1 2 S. A. Cook; Y. Filmus; D. T. M. Le (2012). "The complexity of the comparator circuit value problem". arXiv: 1208.2721 .
  3. 1 2 3 A. Subramanian (1994). "A new approach to stable matching problems". SIAM Journal on Computing. 23 (4): 671–700. doi:10.1137/s0097539789169483.
  4. ↑ Aaronson, Scott (4 July 2014). "The Power of the Digi-Comp II". Shtetl-Optimized. Retrieved 28 July 2014.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.