|
Sipser–Lautemann Theorem
In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that bounded-error probabilistic polynomial (BPP) time is contained in the polynomial time hierarchy, and more specifically Σ2 ∩ Π2. In 1983, Michael Sipser showed that BPP is contained in the polynomial time hierarchy. Péter Gács showed that BPP is actually contained in Σ2 ∩ Π2. Clemens Lautemann contributed by giving a simple proof of BPP’s membership in Σ2 ∩ Π2, also in 1983. It is conjectured that in fact BPP= P, which is a much stronger statement than the Sipser–Lautemann theorem. Proof Here we present the Lautemann's proof. Without loss of generality, a machine ''M'' ∈ BPP with error ≤ 2−, ''x'', can be chosen. (All BPP problems can be amplified to reduce the error probability exponentially.) The basic idea of the proof is to define a Σ2 sentence that is equivalent to stating that ''x'' is in the language, ''L'', defined by ''M'' by usi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Computational Complexity Theory
In theoretical computer science and mathematics, 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 compu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Bounded-error Probabilistic Polynomial
In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest ''practical'' classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine. Informally, a problem is in BPP if there is an algorithm for it that has the following properties: *It is allowed to flip coins and make random decisions *It is guaranteed to run in polynomial time *On any given run of the algorithm, it has a probability of at most 1/3 of giving the wrong answer, whether the answer is YES or NO. Definition A langu ... [...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) which 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 or ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Michael Sipser
Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the Dean of Science at the Massachusetts Institute of Technology. Biography Sipser was born and raised in Brooklyn, New York and moved to Oswego, New York when he was 12 years old. He earned his BA in mathematics from Cornell University in 1974 and his PhD in engineering from the University of California at Berkeley in 1980 under the direction of Manuel Blum.Trafton, Anne"Michael Sipser named dean of the School of Science: Sipser has served as interim dean since Marc Kastner’s departure" MIT News Office, June 5, 2014 He joined MIT's Laboratory for Computer Science as a research associate in 1979 and then was a Research Staff Member at IBM Research in San Jose. In 1980, he joined the MIT faculty. He spent the 1985-1986 academic year on the faculty of the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Clemens Lautemann
Clemens is both a Late Latin masculine given name and a surname meaning "merciful". Notable people with the name include: Surname * Adelaide Clemens (born 1989), Australian actress. * Andrew Clemens (b. 1852 or 1857–1894), American folk artist * Aurelius Prudentius Clemens, 4th century Roman poet * Barry Clemens (born 1943), American basketball player * Bert A. Clemens (1874–1935), American politician * Brian Clemens (born 1931), British screenwriter and television producer * Clayton Clemens, American Professor of Government * Dan Clemens (1945–2019), American politician * Gabriel Clemens (born 1983), German darts player * George T. Clemens (1902–1992), American cinematographer * Harold W. Clemens (1918–1998), American politician * C. Herbert Clemens (born 1939), American mathematician * Isaac Clemens (1815–1880), Canadian farmer and politician * Jacob Clemens non Papa (c. 1510 to 1515–1555 or 1556), Franco-Flemish composer of the Renaissance * James Clemens (disam ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(''n''O(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or " tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb. Definition A language ''L'' is in P if and only if there exists a deterministic Turing machine ''M'', such that * ''M'' runs for polynomial time on all inputs * For all ''x'' in ''L'', ''M'' outputs 1 * For all ''x'' not in ''L'', ''M'' outputs 0 P can also be viewed as a uniform family of boolean circuits. A language ''L'' is in P if and only if there exists a polynomial-time uniform family of boolean circuits \, such that * For all n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Exclusive Disjunction
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , , , , and . The negation of XOR is the logical biconditional, which yields true if and only if the two inputs are the same. It gains the name "exclusive or" because the meaning of "or" is ambiguous when both operands are true; the exclusive or operator ''excludes'' that case. This is sometimes thought of as "one or the other but not both". This could be written as "A or B, but not, A and B". Since it is associative, it may be considered to be an ''n''-ary operator which is true if and only if an odd number of arguments are true. That is, ''a'' XOR ''b'' XOR ... may be treated as XOR(''a'',''b'',...). Truth table The truth table of A XOR B shows that it outputs true whenever the inputs differ: Equivalences, elimination, and introduct ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the ''yes'' and ''no'' answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement problem. For example, one important problem is whether a number is a prime number. Its complement is to determine whether a number is a composite number (a number which is not prime). Here the domain of the complement is the set of all integers exceeding one. There is a Turing reduction from every problem to its complement problem. The complement operation is an involution, meaning it "undoes itself", or the complement of the complement is the original problem. One can generalize this to the complement of a complexity class, called the complement class, which is the set of complements of every problem in the class. If a class is called C, its complement is conventionally labelled co-C ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
S2P (complexity)
In computational complexity theory, S is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language is in \mathsf S_2^P if there exists a polynomial-time predicate ''P'' such that * If x \in L, then there exists a ''y'' such that for all ''z'', P(x,y,z)=1, * If x \notin L, then there exists a ''z'' such that for all ''y'', P(x,y,z)=0, where size of ''y'' and ''z'' must be polynomial of ''x''. Relationship to other complexity classes It is immediate from the definition that S is closed under unions, intersections, and complements. Comparing the definition with that of \Sigma_^P and \Pi_^P, it also follows immediately that S is contained in \Sigma_^P \cap \Pi_^P. This inclusion can in fact be strengthened to ZPPNP.. A preliminary version of this paper appeared earlier, in FOCS 2001, , , . Every language in NP also belongs to For by definition, a language ''L'' is in NP, if and only if there exists a polynomial-time verifier ''V''( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Structural Complexity Theory
In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes. Juris Hartmanis, "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming, 1988 (ICALP 88), ''Lecture Notes in Computer Science'', vol. 317 (1988), pp. 271-286. History The theory has emerged as a result of (still failing) attempts to resolve the first and still the most important question of this kind, the P = NP problem. Most of the research is done basing on the assumption of P not being equal to NP and on a more far-reaching conjecture that the polynomial time hierarchy of complexity classes is infinite. Important results ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |