1.
Travelling salesman problem
–
It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. TSP is a case of the travelling purchaser problem and the vehicle routing problem. In the theory of computational complexity, the version of the TSP belongs to the class of NP-complete problems. Thus, it is possible that the running time for any algorithm for the TSP increases superpolynomially with the number of cities. The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization and it is used as a benchmark for many optimization methods. The TSP has several applications even in its purest formulation, such as planning, logistics, slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. The TSP also appears in astronomy, as observing many sources will want to minimize the time spent moving the telescope between the sources. In many applications, additional constraints such as limited resources or time windows may be imposed, the origins of the travelling salesperson problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, the travelling salesperson problem was mathematically formulated in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman. Hamilton’s Icosian Game was a puzzle based on finding a Hamiltonian cycle. Hassler Whitney at Princeton University introduced the name travelling salesman problem soon after, Dantzig, Fulkerson and Johnson, however, speculated that given a near optimal solution we may be able to find optimality or prove optimality by adding a small amount of extra inequalities. They used this idea to solve their initial 49 city problem using a string model and they found they only needed 26 cuts to come to a solution for their 49 city problem. As well as cutting plane methods, Dantzig, Fulkerson and Johnson used branch, in the following decades, the problem was studied by many researchers from mathematics, computer science, chemistry, physics, and other sciences. Christofides made a big advance in this approach of giving an approach for which we know the worst-case scenario and his algorithm given in 1976, at worst is 1.5 times longer than the optimal solution. As the algorithm was so simple and quick, many hoped it would give way to a optimal solution method. However, until 2011 when it was beaten by less than a billionth of a percent, Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours, great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2392 cities, using cutting planes and branch-and-bound. In the 1990s, Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has used in many recent record solutions
2.
Quantum computing
–
Quantum computing studies theoretical computation systems that make direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from binary digital electronic computers based on transistors, a quantum Turing machine is a theoretical model of such a computer, and is also known as the universal quantum computer. The field of computing was initiated by the work of Paul Benioff and Yuri Manin in 1980, Richard Feynman in 1982. A quantum computer with spins as quantum bits was also formulated for use as a quantum space–time in 1968, there exist quantum algorithms, such as Simons algorithm, that run faster than any possible probabilistic classical algorithm. A classical computer could in principle simulate a quantum algorithm, as quantum computation does not violate the Church–Turing thesis, on the other hand, quantum computers may be able to efficiently solve problems which are not practically feasible on classical computers. A classical computer has a made up of bits, where each bit is represented by either a one or a zero. A quantum computer maintains a sequence of qubits, in general, a quantum computer with n qubits can be in an arbitrary superposition of up to 2 n different states simultaneously. A quantum computer operates by setting the qubits in a drift that represents the problem at hand. The sequence of gates to be applied is called a quantum algorithm, the calculation ends with a measurement, collapsing the system of qubits into one of the 2 n pure states, where each qubit is zero or one, decomposing into a classical state. The outcome can therefore be at most n classical bits of information, Quantum algorithms are often probabilistic, in that they provide the correct solution only with a certain known probability. Note that the term non-deterministic computing must not be used in case to mean probabilistic. An example of an implementation of qubits of a computer could start with the use of particles with two spin states, down and up. This is true because any such system can be mapped onto an effective spin-1/2 system, a quantum computer with a given number of qubits is fundamentally different from a classical computer composed of the same number of classical bits. This means that when the state of the qubits is measured. To better understand this point, consider a classical computer that operates on a three-bit register, if there is no uncertainty over its state, then it is in exactly one of these states with probability 1. However, if it is a computer, then there is a possibility of it being in any one of a number of different states. The state of a quantum computer is similarly described by an eight-dimensional vector. Here, however, the coefficients a k are complex numbers, and it is the sum of the squares of the absolute values, ∑ i | a i |2
3.
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
4.
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
5.
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
6.
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
7.
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
8.
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
9.
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