|
AC0
AC0 (alternating circuit) is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O(1) and polynomial size, with unlimited- fanin AND gates and OR gates (we allow NOT gates only at the inputs). It thus contains NC0, which has only bounded-fanin AND and OR gates. Such circuits are called "alternating circuits", since it is only necessary for the layers to alternate between all-AND and all-OR, since one AND after another AND is equivalent to a single AND, and the same for OR. Example problems Integer addition and subtraction are computable in AC0, but multiplication is not (specifically, when the inputs are two integers under the usual binary or base-10 representations of integers). Since it is a circuit class, like P/poly, AC0 also contains every unary language. Descriptive complexity From a descriptive complexity viewpoint, DLOGTIME-uniform AC0 is equal to the descriptive class FO+BI ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Switching Lemma
In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. It was first introduced by Johan Håstad to prove that AC0, AC0 Boolean circuits of depth ''k'' require size \exp(\Omega(n^)) to compute the parity function on n bits. He was later awarded the Gödel Prize for this work in 1994. The switching lemma describes the behavior of a depth-2 circuit under ''random restriction'', i.e. when randomly fixing most of the coordinates to 0 or 1. Specifically, from the lemma, it follows that a formula in conjunctive normal form (that is, an AND of ORs) becomes a formula in disjunctive normal form (an OR of ANDs) under random restriction, and vice versa. This "switching" gives the lemma its name. Statement Consider a width-w formula in disjunctive normal form F = C_1 \vee C_2 \vee \cdots \vee C_m , the Logical disjunction, OR of clauses C_\ell which are the Logical conjunction, AND of ''w'' literals ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Circuit 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 C_,C_,\ldots (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomial size. Proving that \mathsf\not\subseteq \mathsf would separate P and NP (see below). Complexity classes defined in terms of Boolean circuits include AC0, AC, TC0, NC1, NC, and P/poly. Size and depth A Boolean circuit with n input bits is a directed acyclic graph in which every node (usually called ''gates'' in this context) is either an input node of in-degree 0 l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Descriptive Complexity
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the formal language, languages in them. For example, PH (complexity), PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them. Specifically, each logical system produces a set of query (complexity), queries expressible in it. The queries – when restricted to finite structures – correspond to the computational problems of traditional complexity theory. The first main result of descriptive com ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
FO (complexity)
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them. Specifically, each logical system produces a set of queries expressible in it. The queries – when restricted to finite structures – correspond to the computational problems of traditional complexity theory. The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
AC (complexity)
In circuit complexity, AC is a complexity class hierarchy. Each class, ACi, consists of the languages recognized by Boolean circuits with depth O(\log^i n) and a polynomial number of unlimited fan-in AND and OR gates. The name "AC" was chosen by analogy to NC, with the "A" in the name standing for "alternating" and referring both to the alternation between the AND and OR gates in the circuits and to alternating Turing machines. The smallest AC class is AC0, consisting of constant-depth unlimited fan-in circuits. The total hierarchy of AC classes is defined as \mbox = \bigcup_ \mbox^i Relation to NC The AC classes are related to NC, ACC, and TC classes. For each ''i'', we have, p. 437; , p. 118. :\mathsf^i \subseteq \mathsf^i \subseteq \mathsf^ \subseteq \mathsf^ \subseteq \mathsf^. As an immediate consequence of this, we have that NC = AC = ACC = TC. We have \mathsf^0 \subsetneq \mathsf^0 \subsetneq \mathsf^. Specifically, PARITY is in \mathsf^0 but not in \math ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
BIT Predicate
In mathematics and computer science, the BIT predicate, sometimes is a predicate that tests whether the bit of the (starting from the least significant digit) when i is written as a binary number. Its mathematical applications include modeling the membership relation of hereditarily finite sets, and defining the adjacency relation of the Rado graph. In computer science, it is used for efficient representations of set data structures using bit vectors, in defining the private information retrieval problem from communication complexity, and in descriptive complexity theory to formulate logical descriptions of complexity classes. History The BIT predicate was first introduced in 1937 by Wilhelm Ackermann to define the Ackermann coding, which encodes hereditarily finite sets as The BIT predicate can be used to perform membership tests for the encoded sets: \text(i,j) is true if and only if the set encoded is a member of the set encoded Ackermann denoted the predicate \text( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
LH (complexity)
In computational complexity, the logarithmic time hierarchy (LH) is the complexity class of all computational problems solvable in a logarithmic amount of computation time on an alternating Turing machine with a bounded number of alternations. It is a particular case of a bounded alternating Turing machine hierarchy. It is equal to FO and to FO-uniform AC0. The ith level of the logarithmic time hierarchy is the set of languages recognised by alternating Turing machines in logarithmic time with random access Random access (also called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of addressable elements roughly as easily and efficiently as any other, no matter how many elemen ... and i-1 alternations, beginning with an existential state. LH is the union of all levels. References Complexity classes {{Comp-sci-theory-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can be solved by Turing machines using ''O''(''f''(''n'')) space for some function ''f'' of the input size ''n'', then we can define PSPACE formally asArora & Barak (2009) p.81 :\mathsf = \bigcup_ \mathsf(n^k). It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem,Arora & Barak (2009) p.85 NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a nondeterministic Turing machine without needing much more space (even though it may use much more time).Arora & Barak (2009) p.86 Also, the complements of all problems in PSPACE are also in PSPACE, meaning that co-PSPACE PSPACE. Relation among other classes The following re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Hierarchy
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH. Classes within the hierarchy have complete problems (with respect to polynomial-time reductions) that ask if quantified Boolean formulae hold, for formulae with restrictions on the quantifier order. It is known that equality between classes on the same level or consecutive levels in the hierarchy would imply a "collapse" of the hierarchy to that level. Definitions There are multiple equivalent definitions of the classes of the polynomial hierarchy. Oracle definition For the oracle ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exclusive Or
Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (one is true, one is false). With multiple inputs, XOR is true if and only if the number of true inputs is odd. It gains the name "exclusive or" because the meaning of "or" is ambiguous when both operands are true. XOR ''excludes'' that case. Some informal ways of describing XOR are "one or the other but not both", "either one or the other", and "A or B, but not A and B". It is symbolized by the prefix operator J Translated as and by the infix operators XOR (, , or ), EOR, EXOR, \dot, \overline, \underline, , \oplus, \nleftrightarrow, and \not\equiv. Definition The truth table of A\nleftrightarrow B shows that it outputs true whenever the inputs differ: Equivalences, elimination, and introduction Exclusive disjunction essentially ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
