|
Karp–Lipton Theorem
In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then :\Pi_2 = \Sigma_2 \, and therefore \mathrm = \Sigma_2. \, That is, if we assume that NP, the class of nondeterministic polynomial time problems, can be contained in the non-uniform polynomial time complexity class P/poly, then this assumption implies the collapse of the polynomial hierarchy at its second level. Such a collapse is believed unlikely, so the theorem is generally viewed by complexity theorists as evidence for the nonexistence of polynomial size circuits for SAT or for other NP-complete problems. A proof that such circuits do not exist would imply that P ≠ NP. As P/poly contains all problems solvable in randomized polynomial time (Adleman's theorem), the theorem is also evidence that the use of randomization does not lead to polynomial time algorithms for NP-complete problems. The ... [...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 oracle def ... [...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(''t''(''n'')), the set of all problems that can be solved by Turing machines using ''O''(''t''(''n'')) space for some function ''t'' of the input size ''n'', then we can define PSPACE formally asArora & Barak (2009) p.81 :\mathsf = \bigcup_ \mathsf(n^k). PSPACE is a strict superset of the set of context-sensitive languages. 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 non-deterministic 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 tha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Toda's Theorem
Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" and was given the 1998 Gödel Prize. Statement The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P. Definitions #P is the problem of exactly counting the number of solutions to a polynomially-verifiable question (that is, to a question in NP), while loosely speaking, PP is the problem of giving an answer that is correct more than half the time. The class P#P consists of all the problems that can be solved in polynomial time if you have access to instantaneous answers to any counting problem in #P (polynomial time relative to a #P oracle). Thus Toda's theorem implies that for any problem in the polynomial hierarchy there is a deterministic polynomial-time Turing reduction to a counting problem. An analogous result in the comp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Scott Aaronson
Scott Joel Aaronson (born May 21, 1981) is an American theoretical computer scientist and David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin. His primary areas of research are quantum computing and computational complexity theory. Early life and education Aaronson grew up in the United States, though he spent a year in Asia when his father—a science writer turned public-relations executive—was posted to Hong Kong. He enrolled in a school there that permitted him to skip ahead several years in math, but upon returning to the US, he found his education restrictive, getting bad grades and having run-ins with teachers. He enrolled in The Clarkson School, a gifted education program run by Clarkson University, which enabled Aaronson to apply for colleges while only in his freshman year of high school. He was accepted into Cornell University, where he obtained his BSc in computer science in 2000, [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977. If a decision problem is in PP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial-time algorithm a sufficient (but bounded) number of times. Turing machines that are polynomially-bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial-time machines. This characterization ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cantor's Diagonal Argument
In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument, the anti-diagonal argument, the diagonal method, and Cantor's diagonalization proof, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers. English translation: Such sets are now known as uncountable sets, and the size of infinite sets is now treated by the theory of cardinal numbers which Cantor began. The diagonal argument was not Cantor's first proof of the uncountability of the real numbers, which appeared in 1874. However, it demonstrates a general technique that has since been used in a wide range of proofs, including the first of Gödel's incompleteness theorems and Turing's answer to the ''Entscheidungsproblem''. Diagonalization arguments are often also the source of contradictions like Russell's paradox and Richard's paradox. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Circuit Lower Bounds
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 labelle ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ravi Kannan
Ravindran Kannan ( ta, ரவீந்திரன் கண்ணன்; born 12 March 1953, Madras) is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science. Before joining Microsoft, he was the William K. Lanman Jr. Professor of Computer Science and Professor of Applied Mathematics at Yale University. He has also taught at MIT, Carnegie Mellon University, CMU and Indian Institute of Science, IISc. The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) presented its 2011 Knuth Prize to Ravi Kannan for developing influential algorithmic techniques aimed at solving long-standing computational problems.Micro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Arthur–Merlin Protocol
In computational complexity theory, an Arthur–Merlin protocol, introduced by , is an interactive proof system in which the verifier's coin tosses are constrained to be public (i.e. known to the prover too). proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins. Given two participants in the protocol called Arthur and Merlin respectively, the basic assumption is that Arthur is a standard computer (or verifier) equipped with a random number generating device, while Merlin is effectively an oracle with infinite computational power (also known as a prover). However, Merlin is not necessarily honest, so Arthur must analyze the information provided by Merlin in response to Arthur's queries and decide the problem itself. A problem is considered to be solvable by this protocol if whenever the answer is "yes", Merlin has some series of responses which will cause Arthur to accept at least of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Uwe Schöning
Uwe Schöning (born 28 December 1955) is a retired German computer scientist, known for his research in computational complexity theory. Education and career Schöning earned his Ph.D. from the University of Stuttgart in 1981, under the supervision of Wolfram Schwabhäuser. He was a professor in the Institute for Theoretical Informatics at the University of Ulm until his retirement in 2021. Contributions Schöning introduced the low and high hierarchies to structural complexity theory in 1983. As Schöning later showed in a 1988 paper, these hierarchies play an important role in the complexity of the graph isomorphism problem, which Schöning further developed in a 1993 monograph with Köbler and Toran. In a 1999 Symposium on Foundations of Computer Science, FOCS paper, Schöning showed that WalkSAT, a randomized algorithm previously analyzed for 2-satisfiability by Christos Papadimitriou, Papadimitriou, had good Probabilistic analysis of algorithms, expected time complexity (alth ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Random Self-reducibility
Random self-reducibility (RSR) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances. Definition If for a function ''f'' evaluating any instance ''x'' can be reduced in polynomial time to the evaluation of ''f'' on one or more random instances ''yi'', then it is self-reducible (this is also known as a ''non-adaptive uniform self-reduction''). In a random self-reduction, an arbitrary worst-case instance ''x'' in the domain of ''f'' is mapped to a random set of instances ''y''1, ..., ''yk''. This is done so that ''f''(''x'') can be computed in polynomial time, given the coin-toss sequence from the mapping, ''x'', and ''f''(''y''1), ..., ''f''(''yk''). Therefore, taking the average with respect to the induced distribution on ''yi'', the average-case complexity of ''f'' is the same (within polynomial factors) as the worst-case randomized c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
