|
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 T ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Time 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] |
Vijay Vazirani
Vijay Virkumar Vazirani ( hi, विजय वीरकुमार वज़ीरानी; b. 1957) is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine. Education and career Vazirani first majored in electrical engineering at Indian Institute of Technology, Delhi but in his second year he transferred to MIT and received his bachelor's degree in computer science from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. His dissertation, ''Maximum Matchings without Blossoms'', was supervised by Manuel Blum. After postdoctoral research with Michael O. Rabin and Leslie Valiant at Harvard University, he joined the faculty at Cornell University in 1984. He moved to the IIT Delhi as a full professor in 1990, and moved again to the Georgia Institute of Technology in 1995. He was also a McKay Visiting Professor at the University of California, Be ... [...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] |
Space Complexity
The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely. Similar to time complexity, space complexity is often expressed asymptotically in big O notation, such as O(n), O(n\log n), O(n^\alpha), O(2^n), etc., where is a characteristic of the input influencing space complexity. Space complexity classes Analogously to time complexity classes DTIME(f(n)) and NTIME(f(n)), the complexity classes DSPACE(f(n)) and NSPACE(f(n)) are the sets of languages that are decidable by deterministic (respectively, non-deterministic) Turing machines that use O(f(n)) space. The complexity classes PSPACE and NPSPACE allow f to be any polynomial, analogously to P and NP. That is, :\mathsf = \bigcup_ \mathsf(n^c) and :\mathsf = \bigcup_ \mathsf(n^c) Relationships between classes The space ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Walter Savitch
Walter John Savitch (February 21, 1943 – February 1, 2021) was best known for defining the complexity class NL (nondeterministic logarithmic space), and for Savitch's theorem, which defines a relationship between the NSPACE and DSPACE complexity classes. His work in establishing complexity classes has helped to create the background against which non-deterministic and probabilistic reasoning can be performed. He also did extensive work in the field of natural language processing and mathematical linguistics. He was focused on computational complexity as it applies to genetics and biology for over 10 years. Aside from his work in theoretical computer science, Savitch wrote a number of textbooks for learning to program in C/C++, Java, Ada, Pascal and others. Savitch received his PhD in mathematics from University of California, Berkeley in 1969 under the supervision of Stephen Cook. Since then he was a professor at University of California, San Diego in the computer scie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Savitch's Theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function f\in\Omega(\log(n)), :\mathsf\left(f\left(n\right)\right) \subseteq \mathsf\left(f\left(n\right)^2\right). In other words, if a nondeterministic Turing machine can solve a problem using f(n) space, a deterministic Turing machine can solve the same problem in the square of that space bound.Arora & Barak (2009) p.86 Although it seems that nondeterminism may produce exponential gains in time (as formalized in the unproven exponential time hypothesis In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential t ...), Savitch's theorem shows that it has a markedly more limited effect on space requ ... [...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] |
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 (complexity) , 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. Def ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 hierarchy, polynomial time hierarchy, and more specifically Σ2 ∩ Π2. In 1983, Michael Sipser showed that BPP is contained in the Polynomial hierarchy, 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 (complexity), 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the theoretical areas precisely. The Association for Computing Machinery, ACM's ACM SIGACT, Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description: History While logical inference and mathematical proof had existed previously, in 1931 Kurt Gödel proved with his incompleteness theorem that there are fundamental limitations on what statements could be proved or disproved. Information theory was added to the field with a 1948 mathematical theory of communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of Hebbian learning, learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Isolation Lemma
In theoretical computer science, the term isolation lemma (or isolating lemma) refers to randomized algorithms that reduce the number of solutions to a problem to one, should a solution exist. This is achieved by constructing random constraints such that, with non-negligible probability, exactly one solution satisfies these additional constraints if the solution space is not empty. Isolation lemmas have important applications in computer science, such as the Valiant–Vazirani theorem and Toda's theorem in computational complexity theory. The first isolation lemma was introduced by , albeit not under that name. Their isolation lemma chooses a random number of random hyperplanes, and has the property that, with non-negligible probability, the intersection of any fixed non-empty solution space with the chosen hyperplanes contains exactly one element. This suffices to show the Valiant–Vazirani theorem: there exists a randomized polynomial-time reduction from the Boolean satisfiabilit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
RP (complexity)
In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: * It always runs in polynomial time in the input size * If the correct answer is NO, it always returns NO * If the correct answer is YES, then it returns YES with probability at least 1/2 (otherwise, it returns NO). In other words, the algorithm is allowed to flip a truly random coin while it is running. The only case in which the algorithm can return YES is if the actual answer is YES; therefore if the algorithm terminates and produces YES, then the correct answer is definitely YES; however, the algorithm can terminate with NO ''regardless'' of the actual answer. That is, if the algorithm returns NO, it might be wrong. Some authors call this class R, although this name is more commonly used for the class of recursive languages. If the correct answer is YES and the algorithm is run ''n'' times with the r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
