1.
Computational complexity theory
–
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 the amount of resources needed to solve them, such as time and storage. Other complexity measures are used, such as the amount of communication, the number of gates in a circuit. One of the roles of computational complexity theory is to determine the limits on what computers can. Closely related fields in computer science are analysis of algorithms. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources, a computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a problem is referred to as a problem instance. In computational complexity theory, a problem refers to the question to be solved. In contrast, an instance of this problem is a rather concrete utterance, for example, consider the problem of primality testing. The instance is a number and the solution is yes if the number is prime, stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input. For this reason, complexity theory addresses computational problems and not particular problem instances, when considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet, as in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices and this can be achieved by ensuring that different representations can be transformed into each other efficiently. Decision problems are one of the objects of study in computational complexity theory. A decision problem is a type of computational problem whose answer is either yes or no. A decision problem can be viewed as a language, where the members of the language are instances whose output is yes. The objective is to decide, with the aid of an algorithm, if the algorithm deciding this problem returns the answer yes, the algorithm is said to accept the input string, otherwise it is said to reject the input. An example of a problem is the following
2.
Complexity class
–
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form, the set of problems that can be solved by an abstract machine M using O of resource R, Complexity classes are concerned with the rate of growth of the requirement in resources as the input n increases. It is a measurement, and does not give time or space in requirements in terms of seconds or bytes. The O is read as order of, for the purposes of computational complexity theory, some of the details of the function can be ignored, for instance many possible polynomials can be grouped together as a class. The resource in question can either be time, essentially the number of operations on an abstract machine. The simplest complexity classes are defined by the factors, The type of computational problem. However, complexity classes can be defined based on problems, counting problems, optimization problems, promise problems. The resource that are being bounded and the bounds, These two properties are usually stated together, such as time, logarithmic space, constant depth. Many complexity classes can be characterized in terms of the logic needed to express them. Bounding the computation time above by some function f often yields complexity classes that depend on the chosen machine model. For instance, the language can be solved in time on a multi-tape Turing machine. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that the complexities in any two reasonable and general models of computation are polynomially related. This forms the basis for the complexity class P, which is the set of problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of problems is FP. The Blum axioms can be used to define complexity classes without referring to a computational model. Many important complexity classes can be defined by bounding the time or space used by the algorithm, some important complexity classes of decision problems defined in this manner are the following, It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitchs theorem. #P is an important complexity class of counting problems, classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems, many complexity classes are defined using the concept of a reduction
3.
Algorithm
–
In mathematics and computer science, an algorithm is a self-contained sequence of actions to be performed. Algorithms can perform calculation, data processing and automated reasoning tasks, an algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. The transition from one state to the next is not necessarily deterministic, some algorithms, known as randomized algorithms, giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem. In English, it was first used in about 1230 and then by Chaucer in 1391, English adopted the French term, but it wasnt until the late 19th century that algorithm took on the meaning that it has in modern English. Another early use of the word is from 1240, in a manual titled Carmen de Algorismo composed by Alexandre de Villedieu and it begins thus, Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris. Which translates as, Algorism is the art by which at present we use those Indian figures, the poem is a few hundred lines long and summarizes the art of calculating with the new style of Indian dice, or Talibus Indorum, or Hindu numerals. An informal definition could be a set of rules that precisely defines a sequence of operations, which would include all computer programs, including programs that do not perform numeric calculations. Generally, a program is only an algorithm if it stops eventually, but humans can do something equally useful, in the case of certain enumerably infinite sets, They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. An enumerably infinite set is one whose elements can be put into one-to-one correspondence with the integers, the concept of algorithm is also used to define the notion of decidability. That notion is central for explaining how formal systems come into being starting from a set of axioms. In logic, the time that an algorithm requires to complete cannot be measured, from such uncertainties, that characterize ongoing work, stems the unavailability of a definition of algorithm that suits both concrete and abstract usage of the term. Algorithms are essential to the way computers process data, thus, an algorithm can be considered to be any sequence of operations that can be simulated by a Turing-complete system. Although this may seem extreme, the arguments, in its favor are hard to refute. Gurevich. Turings informal argument in favor of his thesis justifies a stronger thesis, according to Savage, an algorithm is a computational process defined by a Turing machine. Typically, when an algorithm is associated with processing information, data can be read from a source, written to an output device. Stored data are regarded as part of the state of the entity performing the algorithm. In practice, the state is stored in one or more data structures, for some such computational process, the algorithm must be rigorously defined, specified in the way it applies in all possible circumstances that could arise. That is, any conditional steps must be dealt with, case-by-case
4.
Independence (probability theory)
–
In probability theory, two events are independent, statistically independent, or stochastically independent if the occurrence of one does not affect the probability of occurrence of other. Similarly, two variables are independent if the realization of one does not affect the probability distribution of the other. Two events A and B are independent if their joint probability equals the product of their probabilities, although the derived expressions may seem more intuitive, they are not the preferred definition, as the conditional probabilities may be undefined if P or P are 0. Furthermore, the preferred definition makes clear by symmetry that when A is independent of B, B is also independent of A. A finite set of events is independent if every pair of events is independent—that is, if. A finite set of events is independent if every event is independent of any intersection of the other events—that is, if and only if for every n-element subset. This is called the rule for independent events. Note that it is not a condition involving only the product of all the probabilities of all single events. For more than two events, an independent set of events is pairwise independent, but the converse is not necessarily true. Two random variables X and Y are independent if and only if the elements of the π-system generated by them are independent, that is to say, for every a and b, the events and are independent events. A set of variables is pairwise independent if and only if every pair of random variables is independent. A set of variables is mutually independent if and only if for any finite subset X1, …, X n and any finite sequence of numbers a 1, …, a n. The measure-theoretically inclined may prefer to substitute events for events in the above definition and that definition is exactly equivalent to the one above when the values of the random variables are real numbers. It has the advantage of working also for complex-valued random variables or for random variables taking values in any measurable space. Intuitively, two random variables X and Y are conditionally independent given Z if, once Z is known, for instance, two measurements X and Y of the same underlying quantity Z are not independent, but they are conditionally independent given Z. The formal definition of independence is based on the idea of conditional distributions. If X, Y, and Z are discrete random variables, if X and Y are conditionally independent given Z, then P = P for any x, y and z with P >0. That is, the distribution for X given Y and Z is the same as that given Z alone
5.
BPP (complexity)
–
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 time with a deterministic machine. Alternatively, BPP can be defined using only deterministic Turing machines, for some applications this definition is preferable since it does not mention probabilistic Turing machines. In practice, a probability of 1⁄3 might not be acceptable, however. It can be any constant between 0 and 1⁄2 and the set BPP will be unchanged and this makes it possible to create a highly accurate algorithm by merely running the algorithm several times and taking a majority vote of the answers. For example, if one defined the class with the restriction that the algorithm can be wrong with probability at most 1⁄2100, besides the problems in P, which are obviously in BPP, many problems were known to be in BPP but not known to be in P. The number of problems is decreasing, and it is conjectured that P = BPP. For a long time, one of the most famous problems that was known to be in BPP, in other words, is there an assignment of values to the variables such that when a nonzero polynomial is evaluated on these values, the result is nonzero. It suffices to choose each variables value uniformly at random from a subset of at least d values to achieve bounded error probability. If the access to randomness is removed from the definition of BPP, in the definition of the class, if we replace the ordinary Turing machine with a quantum computer, we get the class BQP. Adding postselection to BPP, or allowing computation paths to have different lengths, BPPpath is known to contain NP, and it is contained in its quantum counterpart PostBQP. A Monte Carlo algorithm is an algorithm which is likely to be correct. Problems in the class BPP have Monte Carlo algorithms with polynomial bounded running time and this is compared to a Las Vegas algorithm which is a randomized algorithm which either outputs the correct answer, or outputs fail with low probability. Las Vegas algorithms with polynomial bound running times are used to define the class ZPP, alternatively, ZPP contains probabilistic algorithms that are always correct and have expected polynomial running time. This is weaker than saying it is a polynomial time algorithm, since it may run for super-polynomial time and it is known that BPP is closed under complement, that is, BPP = co-BPP. BPP is low for itself, meaning that a BPP machine with the power to solve BPP problems instantly is not any more powerful than the machine without this extra power. The relationship between BPP and NP is unknown, it is not known whether BPP is a subset of NP, NP is a subset of BPP or neither. If NP is contained in BPP, which is considered unlikely since it would imply practical solutions for NP-complete problems, then NP = RP and it is known that RP is a subset of BPP, and BPP is a subset of PP
6.
NP (complexity)
–
In computational complexity theory, NP is a complexity class used to describe certain types of decision problems. Informally, NP is the set of all decision problems for which the instances where the answer is yes have efficiently verifiable proofs, more precisely, these proofs have to be verifiable by deterministic computations that can be performed in polynomial time. Equivalently, the definition of NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. This second definition is the basis for the abbreviation NP, which stands for nondeterministic, however, the verifier-based definition tends to be more intuitive and practical in common applications compared to the formal machine definition. A method for solving a problem is given in the form of an algorithm. In the above definitions for NP, polynomial time refers to the number of machine operations needed by an algorithm relative to the size of the problem. Polynomial time is therefore a measure of efficiency of an algorithm, decision problems are commonly categorized into complexity classes based on the fastest known machine algorithms. As such, decision problems may change if a faster algorithm is discovered. The most important open question in complexity theory, the P versus NP problem, asks whether polynomial time algorithms actually exist for solving NP-complete and it is widely believed that this is not the case. The complexity class NP is also related to the complexity class co-NP, whether or not NP = co-NP is another outstanding question in complexity theory. The complexity class NP can be defined in terms of NTIME as follows, alternatively, NP can be defined using deterministic Turing machines as verifiers. In particular, the versions of many interesting search problems. In this example, the answer is yes, since the subset of integers corresponds to the sum + +5 =0, the task of deciding whether such a subset with sum zero exists is called the subset sum problem. To answer if some of the integers add to zero we can create an algorithm which obtains all the possible subsets, as the number of integers that we feed into the algorithm becomes larger, the number of subsets grows exponentially and so does the computation time. However, notice that, if we are given a subset, we can easily check or verify whether the subset sum is zero. So if the sum is indeed zero, that particular subset is the proof or witness for the fact that the answer is yes, an algorithm that verifies whether a given subset has sum zero is called verifier. More generally, a problem is said to be in NP if there exists a verifier V for the problem. Given any instance I of problem P, where the answer is yes, there must exist a certificate W such that, given the ordered pair as input, furthermore, if the answer to I is no, the verifier will return no with input for all possible W
7.
P versus NP problem
–
The P versus NP problem is a major unsolved problem in computer science. Informally speaking, it asks whether every problem whose solution can be verified by a computer can also be quickly solved by a computer. The underlying issues were first discussed in the 1950s, in letters from John Nash to the National Security Agency and it is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution. The general class of questions for which some algorithm can provide an answer in time is called class P or just P. For some questions, there is no way to find an answer quickly. The class of questions for which an answer can be verified in polynomial time is called NP, consider the subset sum problem, an example of a problem that is easy to verify, but whose answer may be difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0, for instance, does a subset of the set add up to 0. The answer yes, because the subset adds up to zero can be verified with three additions. There is no algorithm to find such a subset in polynomial time. An answer to the P = NP question would determine whether problems that can be verified in polynomial time, like the subset-sum problem, can also be solved in polynomial time. Although the P versus NP problem was defined in 1971, there were previous inklings of the problems involved, the difficulty of proof. In 1955, mathematician John Nash wrote a letter to the NSA, if proved this would imply what we today would call P ≠ NP, since a proposed key can easily be verified in polynomial time. Another mention of the problem occurred in a 1956 letter written by Kurt Gödel to John von Neumann. The most common resources are time and space, in such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic and sequential, arguably the biggest open question in theoretical computer science concerns the relationship between those two classes, Is P equal to NP. In 2012,10 years later, the poll was repeated. To attack the P = NP question, the concept of NP-completeness is very useful, NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time, and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems, informally, an NP-complete problem is an NP problem that is at least as tough as any other problem in NP
8.
Non-deterministic Turing machine
–
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers. In essence, a Turing machine is imagined to be a computer that reads. It determines what action it should perform next according to its internal state, an example of one of a Turing Machines rules might thus be, If you are in state 2 and you see an A, change it to B and move left. In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation, by contrast, a non-deterministic Turing machine may have a set of rules that prescribes more than one action for a given situation. For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the one position to the right. For example, an X on the tape in state 3 might allow the NTM to write a Y, move right, and switch to state 5, or to write an X, move left, and stay in state 3. L is the movement to the left, and R is to the right, the difference with a standard Turing machine is that for those, the transition relation is a function. How does the NTM know which of these actions it should take, there are two ways of looking at it. One is to say that the machine is the luckiest possible guesser, it always picks a transition that eventually leads to an accepting state, the other is to imagine that the machine branches into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single computation path that it follows, If at least one branch of the tree halts with an accept condition, we say that the NTM accepts the input. NTMs can compute the results as DTMs, that is, they are capable of computing the same values. The time complexity of these varies, however, as is discusssed below. NTMs effectively include DTMs as special cases, so it is clear that DTMs are not more powerful. The 3-tape DTMs are easily simulated with a normal single-tape DTM, therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM. This is considered to be a property of simulations of NTMs by DTMs, the most famous unresolved question in computer science. The time complexity of NTMs is not the same as for DTMs and it is a common misconception that quantum computers are NTMs. It is believed but has not been proven that the power of computers is incomparable to that of NTMs. That is, problems likely exist that an NTM could efficiently solve that a computer cannot
9.
Randomized algorithm
–
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an input to guide its behavior. Formally, the performance will be a random variable determined by the random bits, thus either the running time. In the second case, random performance and random output, the algorithm for a procedure is somewhat questionable. In the case of output, it is no longer formally effective. However, in cases, probabilistic algorithms are the only practical means of solving a problem. As a motivating example, consider the problem of finding an ‘a’ in an array of n elements, input, An array of n≥2 elements, in which half are ‘a’s and the other half are ‘b’s. Output, Find an ‘a’ in the array and we give two versions of the algorithm, one Las Vegas algorithm and one Monte Carlo algorithm. Las Vegas algorithm, This algorithm succeeds with probability 1, after k iterations, the probability of finding an ‘a’ is, This algorithm does not guarantee success, but the run time is bounded. The number of iterations is less than or equal to k. Taking k to be constant the run time is Θ, Randomized algorithms are particularly useful when faced with a malicious adversary or attacker who deliberately tries to feed a bad input to the algorithm such as in the Prisoners dilemma. It is for this reason that randomness is ubiquitous in cryptography, in cryptographic applications, pseudo-random numbers cannot be used, since the adversary can predict them, making the algorithm effectively deterministic. Therefore, either a source of random numbers or a cryptographically secure pseudo-random number generator is required. Another area in which randomness is inherent is quantum computing, in the example above, the Las Vegas algorithm always outputs the correct answer, but its running time is a random variable. The Monte Carlo algorithm is guaranteed to complete in an amount of time that can be bounded by a function the size and its parameter k. Observe that any Las Vegas algorithm can be converted into a Monte Carlo algorithm, by having it output an arbitrary, Computational complexity theory models randomized algorithms as probabilistic Turing machines. Both Las Vegas and Monte Carlo algorithms are considered, and several complexity classes are studied, the complement class for RP is co-RP. Problem classes having algorithms with polynomial time average case running time whose output is always correct are said to be in ZPP, the class of problems for which both YES and NO-instances are allowed to be identified with some error is called BPP
10.
Michael O. Rabin
–
Michael Oser Rabin, is an Israeli computer scientist and a recipient of the Turing Award. Rabin was born in 1931 in Breslau, Germany, the son of a rabbi, in 1935, he emigrated with his family to Mandate Palestine. After high school, he was drafted into the army during the 1948 Arab–Israeli War, the mathematician Abraham Fraenkel, who was a professor of mathematics in Jerusalem, intervened with the army command, and Rabin was discharged to study at the university in 1949. He received an M. Sc. from Hebrew University of Jerusalem in 1953 and he became Associate Professor of Mathematics at the University of California, Berkeley and MIT. Before moving to Harvard University as Gordon McKay Professor of Computer Science in 1981, in the late 1950s, he was invited for a summer to do research for IBM at the Lamb Estate in Westchester County, New York with other promising mathematicians and scientists. It was there that he and Dana Scott wrote the paper Finite Automata, soon, using nondeterministic automata, they were able to re-prove Kleenes result that finite state machines exactly accept regular languages. As to the origins of what was to become computational complexity theory, nondeterministic machines have become a key concept in computational complexity theory, particularly with the description of complexity classes P and NP. Rabin then returned to Jerusalem, researching logic, and working on the foundations of what would later be known as computer science. He was a professor and the head of the Institute of Mathematics at the Hebrew University at 29 years old. Rabin recalls, There was absolutely no appreciation of the work on the issues of computing, mathematicians did not recognize the emerging new field. In 1960, he was invited by Edward F. Moore to work at Bell Labs, where Rabin introduced probabilistic automata that employ coin tosses in order to decide which state transitions to take. He showed examples of languages that required a very large number of states. In 1969, Rabin proved that the theory of n successors is decidable. A key component of the proof implicitly showed determinacy of parity games, in 1975, Rabin finished his tenure as Rector of the Hebrew University of Jerusalem and went to the Massachusetts Institute of Technology in the USA as a visiting professor. Gary Miller was also there and had his polynomial time test for primality based on the extended Riemann hypothesis, while there, Rabin invented the Miller-Rabin primality test, a randomized algorithm that can determine very quickly whether a number is prime. In 1976 he was invited by Joseph Traub to meet at Carnegie Mellon University, after he gave that lecture, Traub had said, No, no, this is revolutionary, and its going to become very important. In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization. In 1987, Rabin, together with Richard Karp, created one of the most well-known efficient string search algorithms, rabins more recent research has concentrated on computer security
11.
William Gasarch
–
William Ian Gasarch is a computer scientist known for his work in computational complexity theory, computability theory, computational learning theory, and Ramsey theory. He is currently a professor at the University of Maryland Department of Computer Science with an appointment in Mathematics. As of 2015 he has supervised over 40 high school students on projects, including Jacob Lurie. He has co-blogged on computational complexity with Lance Fortnow since 2007 and he was the book review editor for ACM SIGACT NEWS from 1997-2015 before resigning and turning the job over to Fred Green, a professor of Computer science at Clark University. William Gasarch received his doctorate in science from Harvard in 1985. His thesis was titled Recursion-Theoretic Techniques in Complexity Theory and Combinatorics and he was hired into a tenure track professorial job at the University of Maryland in the Fall of 1985. He was promoted to Associate Professor with Tenure in 1991, and he also co-founded the subfield of recursion-theoretic inductive inference named Learning via Queries with Carl Smith. More recently he has been involved with combinatorics, notably Ramsey Theory. He has written two surveys of what theorists think of the P vs NP problem, Lance Fortnow began writing a blog on theoretical computer science with an emphasis on complexity theory in 2003. William Gasarch was a frequent guest blogger until 2007 when he became an official co-blogger, largely because of the blog Fortnow/Gasarch were named one of the 50 most social-media savvy professors in America. Their blog is one of the top 30 computer science. He has the largest collection of satires of Bob Dylans music
12.
AC0
–
AC0 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 and polynomial size, with unlimited-fanin AND gates and it thus contains NC0, which has only bounded-fanin AND and OR gates. Integer addition and subtraction are computable in AC0, but multiplication is not, in 1984 Furst, Saxe, and Sipser showed that calculating the parity of an input cannot be decided by any AC0 circuits, even with non-uniformity. It follows that AC0 is not equal to NC1, because a family of circuits in the class can compute parity. More precise bounds follow from switching lemma, using them, it has been shown that there is an oracle separation between the polynomial hierarchy and PSPACE
13.
ACC0
–
ACC0, sometimes called ACC, is a class of computational models and problems defined in circuit complexity, a field of theoretical computer science. The class is defined by augmenting the class AC0 of constant-depth alternating circuits with the ability to count, specifically, a problem belongs to ACC0 if it can be solved by polynomial-size, constant-depth circuits of unbounded fan-in gates, including gates that count modulo a fixed integer. ACC0 corresponds to computation in any solvable monoid, more formally, a language belongs to AC0 if it can be computed by a family of circuits C1, C2. A language belongs to ACC0 if it belongs to AC0 for some m, in some texts, ACCi refers to a hierarchy of circuit classes with ACC0 at its lowest level, where the circuits in ACCi have depth O and polynomial size. The class ACC0 can also be defined in terms of computations of nonuniform deterministic finite automata over monoids. In this framework, the input is interpreted as elements from a fixed monoid, the class ACC0 is the family of languages accepted by a NUDFA over some monoid that does not contain an unsolvable group as a subsemigroup. This inclusion is strict, because a single MOD-2 gate computes the parity function, more generally, the function MODm can not be computed in AC0 for prime p unless m is a power of p. The class ACC0 is included in TC0 and it is conjectured that ACC0 is unable to compute the majority function of its inputs, but this remains unresolved as of July 2014. Every problem in ACC0 can be solved by circuits of depth 2, with AND gates of polylogarithmic fan-in at the inputs, the proof follows ideas of the proof of Todas theorem. Williams proves that ACC0 does not contain NEXPTIME, the proof uses many results in complexity theory, including the time hierarchy theorem, IP = PSPACE, derandomization, and the representation of ACC0 via SYM+ circuits. It is known that computing the permanent is impossible for logtime-uniform ACC0 circuits, which implies that the complexity class PP is not contained in logtime-uniform ACC0
14.
CC (complexity)
–
In computational complexity theory, CC is the complexity class containing decision problems which can be solved by comparator circuits of polynomial size. The most important problem which is complete for CC is a variant of the stable marriage problem. 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 input to any wire can be either a variable, its negation, one of the wires is designated as the output wire. The comparator circuit value problem is the problem of evaluating a comparator circuit given an encoding of the circuit, the complexity class CC is defined as the class of problems logspace reducible to CCVP. An equivalent definition is the class of problems AC0 reducible to CCVP, since there are sorting networks which can be constructed in AC0, this shows that the majority function is in CC. 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 is CC-complete. In the stable marriage problem, there is a 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. Among the stable matchings, there is one in each woman gets the best man that she ever gets in any stable matching. The decision version of the matching problem is, given the rankings of all men and women, whether a given man. Although the classical Gale–Shapley algorithm cannot be implemented as a comparator circuit, another problem which is CC-complete is lexicographically-first maximal matching. In this problem, we are given a graph with an order on the vertices. 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 model is CC-complete. The problem is to decide whether any pebbles are present in a particular pile after executing the program and 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. The comparator circuit evaluation problem can be solved in polynomial time, on the other hand, comparator circuits can solve directed reachability, and so CC contains NL. There is a world in which CC and NC are incomparable
15.
BQP
–
In computational complexity theory, BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the analogue of the complexity class BPP. In other words, there is an algorithm for a computer that solves the decision problem with high probability and is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/3 that it give the wrong answer. Similarly to other bounded error probabilistic classes the choice of 1/3 in the definition is arbitrary and we can run the algorithm a constant number of times and take a majority vote to achieve any desired probability of correctness less than 1, using the Chernoff bound. BQP can also be viewed as the associated with certain bounded-error uniform families of quantum circuits. For example, algorithms are known for factoring an n-bit integer using just over 2n qubits, usually, computation on a quantum computer ends with a measurement. This leads to a collapse of state to one of the basis states. It can be said that the state is measured to be in the correct state with high probability. Quantum computers have gained widespread interest because some problems of practical interest are known to be in BQP, just like P and BPP, BQP is low for itself, which means BQPBQP = BQP. Informally, this is true because polynomial time algorithms are closed under composition, if a polynomial time algorithm calls as a subroutine polynomially many polynomial time algorithms, the resulting algorithm is still polynomial time. BQP contains P and BPP and is contained in AWPP, PP, the relation between BQP and NP is not known. Adding postselection to BQP results in the complexity class PostBQP which is equal to PP
16.
NP-completeness
–
In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC, the abbreviation NP refers to nondeterministic polynomial time. That is, the required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether or not it is possible to solve problems quickly. NP-complete problems are addressed by using heuristic methods and approximation algorithms. A problem p in NP is NP-complete if every problem in NP can be transformed into p in polynomial time. NP-complete problems are studied because the ability to quickly verify solutions to a problem seems to correlate with the ability to solve that problem. It is not known whether every problem in NP can be quickly solved—this is called the P versus NP problem, because of this, it is often said that NP-complete problems are harder or more difficult than NP problems in general. A decision problem C is NP-complete if, C is in NP, C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NP-hard, a consequence of this definition is that if we had a polynomial time algorithm for C, we could solve all problems in NP in polynomial time. The concept of NP-completeness was introduced in 1971, though the term NP-complete was introduced later, at 1971 STOC conference, there was a fierce debate among the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine. This is known as the question of whether P=NP, nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics. The Clay Mathematics Institute is offering a US $1 million reward to anyone who has a proof that P=NP or that P≠NP. Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete, in 1972, Richard Karp proved that several other problems were also NP-complete, thus there is a class of NP-complete problems. For more details refer to Introduction to the Design and Analysis of Algorithms by Anany Levitin, an interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices, consider these two problems, Graph Isomorphism, Is graph G1 isomorphic to graph G2. Subgraph Isomorphism, Is graph G1 isomorphic to a subgraph of graph G2, the Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete and this is an example of a problem that is thought to be hard, but is not thought to be NP-complete
17.
NP-hardness
–
NP-hardness, in computational complexity theory, is the defining property of a class of problems that are, informally, at least as hard as the hardest problems in NP. As a consequence, finding an algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP. A common misconception is that the NP in NP-hard stands for non-polynomial when in fact it stands for Non-deterministic Polynomial acceptable problems, although it is suspected that there are no polynomial-time algorithms for NP-hard problems, this has never been proven. Moreover, the class P in which all problems can be solved in time, is contained in the NP class. Informally, we can think of an algorithm that can call such a machine as a subroutine for solving H. Another definition is to require that there is a reduction from an NP-complete problem G to H. As any problem L in NP reduces in polynomial time to G, L reduces in turn to H in polynomial time so this new definition implies the previous one. Awkwardly, it does not restrict the class NP-hard to decision problems, for instance it also includes search problems, If P ≠ NP, then NP-hard problems cannot be solved in polynomial time. Note that some NP-hard optimization problems can be polynomial-time approximated up to some constant approximation ratio or even up to any approximation ratio. An example of an NP-hard problem is the subset sum problem. That is a problem, and happens to be NP-complete. Another example of an NP-hard problem is the problem of finding the least-cost cyclic route through all nodes of a weighted graph. This is commonly known as the traveling salesman problem, there are decision problems that are NP-hard but not NP-complete, for example the halting problem. This is the problem which asks given a program and its input and that is a yes/no question, so this is a decision problem. It is easy to prove that the problem is NP-hard. It is also easy to see that the problem is not in NP since all problems in NP are decidable in a finite number of operations, while the halting problem. There are also NP-hard problems that are neither NP-complete nor undecidable, for instance, the language of True quantified Boolean formulas is decidable in polynomial space, but not non-deterministic polynomial time. NP-hard problems do not have to be elements of the complexity class NP, NP-hard Class of decision problems which are at least as hard as the hardest problems in NP
18.
QMA
–
In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the nonprobabilistic complexity class NP or the probabilistic complexity class MA. It is related to BQP in the same way NP is related to P, moreover, when the answer is NO, every polynomial-size quantum state is rejected by the verifier with high probability. As is usually the case, the constants 2/3 and 1/3 can be changed, changing 2/3 to any constant strictly between 1/2 and 1, or changing 1/3 to any constant strictly between 0 and 1/2, does not change the class QMA. ∀ x ∉ L, for all quantum states | ψ ⟩, the complexity class QMA is defined to be equal to QMA. However, the constants are not too important since the class remains unchanged if c and s are set to any constants such that c is greater than s, moreover, for any polynomials q and r, we have QMA = QMA = QMA. Since many interesting classes are contained in QMA, such as P, BQP and NP, however, there are problems that are in QMA but not known to be in NP or BQP. Some such well known problems are discussed below, a problem is said to be QMA-hard, analogous to NP-hard, if every problem in QMA can be reduced to it. A problem is said to be QMA-complete if it is QMA-hard, the local Hamiltonian problem is the quantum analogue of MAX-SAT. A Hamiltonian is a Hermitian matrix acting on states, thus it is 2 n ×2 n for a system of n qubits. A k-local Hamiltonian is a Hamiltonian which can be written as the sum of Hamiltonians, the k-local Hamiltonian problem, which is a promise problem, is defined as follows. The input is a k-local Hamiltonian acting on n qubits, which is the sum of polynomially many Hermitian matrices that act on only k qubits, the input also contains two numbers a < b ∈, such that 1 b − a = O for some constant c. The problem is to determine whether the smallest eigenvalue of this Hamiltonian is less than a or greater than b, the k-local Hamiltonian is QMA-complete for k ≥2. Such models are applicable to universal adiabatic quantum computation, the Hamiltonians for the QMA-complete problem can also be restricted to act on a two dimensional grid of qubits or a line of quantum particles with 12 states per particle. A list of known QMA-complete problems can be found at http, QCMA, which stands for Quantum Classical Merlin Arthur, is similar to QMA, but the proof has to be a classical string. It is not known whether QMA equals QCMA, although QCMA is clearly contained in QMA, QIP, which stands for Quantum Interactive Polynomial time, is a generalization of QMA where Merlin and Arthur can interact for k rounds. QIP is known to be in PSPACE, QIP is QIP where k is allowed to be polynomial in the number of qubits. It is known that QIP = QIP and it is also known that QIP = IP = PSPACE. The next two inclusions follow from the fact that the verifier is being more powerful in each case
19.
IP (complexity)
–
In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of a proof system was first introduced by Shafi Goldwasser, Silvio Micali. These two machines exchange a number, p, of messages and once the interaction is completed. At most two additional rounds of interaction are required to replicate the effect of a private-coin protocol, the opposite inclusion is straightforward, because the verifier can always send to the prover the results of their private coin tosses, which proves that the two types of protocols are equivalent. The proof can be divided in two parts, we show that IP ⊆ PSPACE and PSPACE ⊆ IP, in order to demonstrate that IP ⊆ PSPACE, we present a simulation of an interactive proof system by a polynomial space machine. This expression is the average of NMj+1, weighted by the probability that the verifier sent message mj+1, take M0 to be the empty message sequence, here we will show that NM0 can be computed in polynomial space, and that NM0 = Pr. First, to compute NM0, an algorithm can calculate the values NMj for every j. Since the depth of the recursion is p, only polynomial space is necessary, the second requirement is that we need NM0 = Pr, the value needed to determine whether w is in A. We use induction to prove this as follows and we must show that for every 0 ≤ j ≤ p and every Mj, NMj = Pr, and we will do this using induction on j. The base case is to prove for j = p, then we will use induction to go from p down to 0. The base case of j = p is fairly simple, since mp is either accept or reject, if mp is accept, NMp is defined to be 1 and Pr =1 since the message stream indicates acceptance, thus the claim is true. If mp is reject, the argument is very similar, for the inductive hypothesis, we assume that for some j+1 ≤ p and any message sequence Mj+1, NMj = Pr and then prove the hypothesis for j and any message sequence Mj. If j is even, mj+1 is a message from V to P, by the definition of NMj, N M j = ∑ m j +1 Pr r N M j +1. Then, by the hypothesis, we can say this is equal to ∑ m j +1 Pr r ∗ Pr. Finally, by definition, we can see that this is equal to Pr, If j is odd, mj+1 is a message from P to V. By definition, N M j = max m j +1 N M j +1, then, by the inductive hypothesis, this equals max m j +1 ∗ Pr. This is equal to Pr since, max m j +1 Pr ≤ Pr because the prover on the side could send the message mj+1 to maximize the expression on the left-hand side. And, max m j +1 Pr ≥ Pr Since the same Prover cannot do any better than send that same message, thus, this holds whether i is even or odd and the proof that IP ⊆ PSPACE is complete
20.
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. PSPACE is a 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 Savitchs theorem, NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a non-deterministic Turing machine without needing much more space. Also, the complements of all problems in PSPACE are also in PSPACE and it is widely suspected that all are strict. The containments in the line are both known to be strict. The first follows from direct diagonalization and the fact that PSPACE = NPSPACE via Savitchs theorem, the second follows simply from the space hierarchy theorem. The hardest problems in PSPACE are the PSPACE-Complete problems, see PSPACE-Complete for examples of problems that are suspected to be in PSPACE but not in NP. The class PSPACE is closed under union, complementation. An alternative characterization of PSPACE is the set of problems decidable by an alternating Turing machine in polynomial time, a logical characterization of PSPACE from descriptive complexity theory is that it is the set of problems expressible in second-order logic with the addition of a transitive closure operator. A full transitive closure is not needed, a transitive closure. It is the addition of this operator that distinguishes PSPACE from PH, a major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particular interactive proof system, the one defining the class IP. In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language, PSPACE can be characterized as the quantum complexity class QIP. PSPACE is also equal to PCTC, problems solvable by classical computers using closed curves, as well as to BQPCTC. PSPACE-complete problems are of importance to studying PSPACE problems because they represent the most difficult problems in PSPACE. Finding a simple solution to a PSPACE-complete problem would mean we have a solution to all other problems in PSPACE because all PSPACE problems could be reduced to a PSPACE-complete problem. An example of a PSPACE-complete problem is the quantified Boolean formula problem, introduction to the Theory of Computation. Chapter 19, Polynomial space, pp. 455–490, introduction to the Theory of Computation. Chapter 8, Space Complexity Complexity Zoo, PSPACE