Misplaced Pages

#712287

111-408: In computational complexity , problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate , and the class of such problems is called NPI . Ladner's theorem , shown in 1975 by Richard E. Ladner , is a result asserting that, if P ≠ NP , then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it

222-555: A are witnesses of compositeness of n ). These are also compositeness tests. The Miller–Rabin primality test works as follows: Given an integer n , choose some positive integer a  <  n . Let 2 d = n  − 1, where d is odd. If and then n is composite and a is a witness for the compositeness. Otherwise, n may or may not be prime. The Miller–Rabin test is a strong probable prime test (see PSW page 1004). The Solovay–Strassen primality test uses another equality: Given an odd number n , choose some integer

333-422: A formal language , where the members of the language are instances whose output is yes, and the non-members are those instances whose output is no. The objective is to decide, with the aid of an algorithm , whether a given input string is a member of the formal language under consideration. If the algorithm deciding this problem returns the answer yes , the algorithm is said to accept the input string, otherwise it

444-584: A  <  n , if then n is composite and a is a witness for the compositeness. Otherwise, n may or may not be prime. The Solovay–Strassen test is an Euler probable prime test (see PSW page 1003). For each individual value of a , the Solovay–Strassen test is weaker than the Miller–Rabin test. For example, if n = 1905 and a = 2, then the Miller-Rabin test shows that n is composite, but

555-720: A Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory. Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines , probabilistic Turing machines , non-deterministic Turing machines , quantum Turing machines , symmetric Turing machines and alternating Turing machines . They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others. A deterministic Turing machine

666-460: A computational resource. Complexity measures are very generally defined by the Blum complexity axioms . Other complexity measures used in complexity theory include communication complexity , circuit complexity , and decision tree complexity . The complexity of an algorithm is often expressed using big O notation . The best, worst and average case complexity refer to three different ways of measuring

777-402: A counterexample. Probabilistic tests are more rigorous than heuristics in that they provide provable bounds on the probability of being fooled by a composite number. Many popular primality tests are probabilistic tests. These tests use, apart from the tested number n , some other numbers a which are chosen at random from some sample space ; the usual randomized primality tests never report

888-435: A divisor less than or equal to n {\displaystyle {\sqrt {n}}} , so the algorithm need only search for divisors less than or equal to n {\displaystyle {\sqrt {n}}} to guarantee detection of all divisor pairs. Also, 2 is a prime dividing 100, which immediately proves that 100 is not prime. Every positive integer except 1 is divisible by at least one prime number by

999-506: A factor. In 1975, Vaughan Pratt showed that there existed a certificate for primality that was checkable in polynomial time, and thus that PRIMES was in NP , and therefore in ⁠ N P ∩ c o N P {\displaystyle {\mathsf {NP\cap coNP}}} ⁠ . See primality certificate for details. The subsequent discovery of the Solovay–Strassen and Miller–Rabin algorithms put PRIMES in coRP . In 1992,

1110-519: A given graph. The exponential time hypothesis also implies that no quasi-polynomial-time problem can be NP-complete, so under this assumption these problems must be NP-intermediate. 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 their computational complexity , i.e.,

1221-623: A heuristic argument by Hendrik Lenstra and Carl Pomerance suggests that it is probably false. A modified version of the Agrawal's conjecture, the Agrawal–Popovych conjecture, may still be true. In computational complexity theory , the formal language corresponding to the prime numbers is denoted as PRIMES. It is easy to show that PRIMES is in Co-NP : its complement COMPOSITES is in NP because one can decide compositeness by nondeterministically guessing

SECTION 10

#1733085330713

1332-580: A large-scale method, n {\displaystyle n} can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped. A simple but very inefficient primality test uses Wilson's theorem , which states that p {\displaystyle p} is prime if and only if: Although this method requires about p {\displaystyle p} modular multiplications, rendering it impractical, theorems about primes and modular residues form

1443-409: A member of this set corresponds to solving the problem of multiplying two numbers. To measure the difficulty of solving a computational problem, one may wish to see how much time the best algorithm requires to solve the problem. However, the running time may, in general, depend on the instance. In particular, larger instances will require more time to solve. Thus the time required to solve a problem (or

1554-462: A number is prime, while others like Miller–Rabin prove that a number is composite . Therefore, the latter might more accurately be called compositeness tests instead of primality tests. The simplest primality test is trial division : given an input number, n {\displaystyle n} , check whether it is divisible by any prime number between 2 and n {\displaystyle {\sqrt {n}}} (i.e., whether

1665-675: A number is prime. The algorithm is prohibitively slow in practice. If quantum computers were available, primality could be tested asymptotically faster than by using classical computers. A combination of Shor's algorithm , an integer factorization method, with the Pocklington primality test could solve the problem in O ( ( log ⁡ n ) 3 ( log ⁡ log ⁡ n ) 2 log ⁡ log ⁡ log ⁡ n ) {\displaystyle O((\log n)^{3}(\log \log n)^{2}\log \log \log n)} . Near

1776-426: A particular algorithm falls under the field of analysis of algorithms . To show an upper bound T ( n ) {\displaystyle T(n)} on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most T ( n ) {\displaystyle T(n)} . However, proving lower bounds is much more difficult, since lower bounds make

1887-415: A polynomial-time algorithm. A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if

1998-493: A prime number as composite, but it is possible for a composite number to be reported as prime. The probability of error can be reduced by repeating the test with several independently chosen values of a ; for two commonly used tests, for any composite n at least half the a ' s detect n ' s compositeness, so k repetitions reduce the error probability to at most 2 , which can be made arbitrarily small by increasing k . The basic structure of randomized primality tests

2109-509: A problem being at most as difficult as another problem. For instance, if a problem X {\displaystyle X} can be solved using an algorithm for Y {\displaystyle Y} , X {\displaystyle X} is no more difficult than Y {\displaystyle Y} , and we say that X {\displaystyle X} reduces to Y {\displaystyle Y} . There are many different types of reductions, based on

2220-459: A problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis . Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine , Conway's Game of Life , cellular automata , lambda calculus or any programming language can be computed on

2331-419: A problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing . The instance is a number (e.g., 15) and the solution is "yes" if the number is prime and "no" otherwise (in this case, 15 is not prime and the answer is "no"). Stated another way,

SECTION 20

#1733085330713

2442-411: A problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory:

2553-510: A round of Miller–Rabin, but achieves a probability bound comparable to seven rounds of Miller–Rabin. The Frobenius test is a generalization of the Lucas probable prime test. The Baillie–PSW primality test is a probabilistic primality test that combines a Fermat or Miller–Rabin test with a Lucas probable prime test to get a primality test that has no known counterexamples. That is, there are no known composite n for which this test reports that n

2664-499: A statement about all possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of T ( n ) {\displaystyle T(n)} for a problem requires showing that no algorithm can have time complexity lower than T ( n ) {\displaystyle T(n)} . Upper and lower bounds are usually stated using

2775-432: Is prime . Among other fields of mathematics , it is used for cryptography . Unlike integer factorization , primality tests do not generally give prime factors , only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that

2886-438: Is a computational problem where a single output (of a total function ) is expected for every input, but the output is more complex than that of a decision problem —that is, the output is not just yes or no. Notable examples include the traveling salesman problem and the integer factorization problem . It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this

2997-401: Is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model

3108-449: Is a set of problems of related complexity. Simpler complexity classes are defined by the following factors: Some complexity classes have complicated definitions that do not fit into this framework. Thus, a typical complexity class has a definition like the following: But bounding the computation time above by some concrete function f ( n ) {\displaystyle f(n)} often yields complexity classes that depend on

3219-852: Is almost three times as fast as testing all numbers up to n {\displaystyle {\sqrt {n}}} . Generalizing further, all primes greater than c # {\displaystyle c\#} ( c primorial ) are of the form c # ⋅ k + i {\displaystyle c\#\cdot k+i} for i , k {\displaystyle i,k} positive integers, 0 ≤ i < c # {\displaystyle 0\leq i<c\#} , and i {\displaystyle i} coprime to c # {\displaystyle c\#} . For example, consider 6 # = 2 ⋅ 3 ⋅ 5 = 30 {\displaystyle 6\#=2\cdot 3\cdot 5=30} . All integers are of

3330-592: Is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty. Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property: Schaefer's dichotomy theorem provides conditions under which classes of constrained Boolean satisfiability problems cannot be in NPI. Some problems that are considered good candidates for being NP-intermediate are

3441-459: Is as follows: After one or more iterations, if n is not found to be a composite number, then it can be declared probably prime . The simplest probabilistic primality test is the Fermat primality test (actually a compositeness test). It works as follows: If a (modulo n ) is 1 but n is not prime, then n is called a pseudoprime to base a . In practice, if a (modulo n ) is 1, then n

NP-intermediate - Misplaced Pages Continue

3552-522: Is at most f ( n ) {\displaystyle f(n)} . A decision problem A {\displaystyle A} can be solved in time f ( n ) {\displaystyle f(n)} if there exists a Turing machine operating in time f ( n ) {\displaystyle f(n)} that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance,

3663-414: Is because a polynomial-time solution to Π 1 {\displaystyle \Pi _{1}} would yield a polynomial-time solution to Π 2 {\displaystyle \Pi _{2}} . Similarly, because all NP problems can be reduced to the set, finding an NP-complete problem that can be solved in polynomial time would mean that P = NP. The complexity class P

3774-877: Is believed that N P {\displaystyle NP} is not equal to c o - N P {\displaystyle co{\text{-}}NP} ; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then P {\displaystyle P} is not equal to N P {\displaystyle NP} , since P = c o - P {\displaystyle P=co{\text{-}}P} . Thus if P = N P {\displaystyle P=NP} we would have c o - P = c o - N P {\displaystyle co{\text{-}}P=co{\text{-}}NP} whence N P = P = c o - P = c o - N P {\displaystyle NP=P=co{\text{-}}P=co{\text{-}}NP} . Similarly, it

3885-410: Is defined to be the maximum time taken over all inputs of size n {\displaystyle n} . If T ( n ) {\displaystyle T(n)} is a polynomial in n {\displaystyle n} , then the algorithm is said to be a polynomial time algorithm. Cobham's thesis argues that a problem can be solved with a feasible amount of resources if it admits

3996-424: Is harder than X {\displaystyle X} , since an algorithm for X {\displaystyle X} allows us to solve any problem in C {\displaystyle C} . The notion of hard problems depends on the type of reduction being used. For complexity classes larger than P, polynomial-time reductions are commonly used. In particular, the set of problems that are hard for NP

4107-570: Is in N P {\displaystyle NP} and in c o - N P {\displaystyle co{\text{-}}NP} (and even in UP and co-UP ). If the problem is N P {\displaystyle NP} -complete, the polynomial time hierarchy will collapse to its first level (i.e., N P {\displaystyle NP} will equal c o - N P {\displaystyle co{\text{-}}NP} ). The best known algorithm for integer factorization

4218-940: Is needed in order to increase the number of problems that can be solved. More precisely, the time hierarchy theorem states that D T I M E ( o ( f ( n ) ) ) ⊊ D T I M E ( f ( n ) ⋅ log ⁡ ( f ( n ) ) ) {\displaystyle {\mathsf {DTIME}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log(f(n)){\big )}} . The space hierarchy theorem states that D S P A C E ( o ( f ( n ) ) ) ⊊ D S P A C E ( f ( n ) ) {\displaystyle {\mathsf {DSPACE}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n){\big )}} . The time and space hierarchy theorems form

4329-439: Is not known if L {\displaystyle L} (the set of all problems that can be solved in logarithmic space) is strictly contained in P {\displaystyle P} or equal to P {\displaystyle P} . Again, there are many complexity classes between the two, such as N L {\displaystyle NL} and N C {\displaystyle NC} , and it

4440-421: Is not known if they are distinct or equal classes. It is suspected that P {\displaystyle P} and B P P {\displaystyle BPP} are equal. However, it is currently open if B P P = N E X P {\displaystyle BPP=NEXP} . Primality testing A primality test is an algorithm for determining whether an input number

4551-501: Is not known whether it lies in classes lying inside P such as NC or L . It is known that PRIMES is not in AC . Certain number-theoretic methods exist for testing whether a number is prime, such as the Lucas test and Proth's test . These tests typically require factorization of n  + 1, n − 1, or a similar quantity, which means that they are not useful for general-purpose primality testing, but they are often quite powerful when

NP-intermediate - Misplaced Pages Continue

4662-599: Is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see non-deterministic algorithm . Many machine models different from the standard multi-tape Turing machines have been proposed in the literature, for example random-access machines . Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary. What all these models have in common

4773-549: Is not prime, even though 17 is coprime to 7 # = 2 ⋅ 3 ⋅ 5 ⋅ 7 {\displaystyle 7\#=2\cdot 3\cdot 5\cdot 7} . As c {\displaystyle c} grows, the fraction of coprime remainders to remainders decreases, and so the time to test n {\displaystyle n} decreases (though it still necessary to check for divisibility by all primes that are less than c {\displaystyle c} ). Observations analogous to

4884-429: Is not prime. In cases where it is not feasible to compute the list of primes ≤ n {\displaystyle \leq {\sqrt {n}}} , it is also possible to simply (and slowly) check all numbers between 2 {\displaystyle 2} and n {\displaystyle {\sqrt {n}}} for divisors. A rather simple optimization is to test divisibility by 2 and by just

4995-401: Is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples ( a , b , c ) {\displaystyle (a,b,c)} such that the relation a × b = c {\displaystyle a\times b=c} holds. Deciding whether a given triple is

5106-471: Is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 km. 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 (i.e.,

5217-598: Is of the form 6 k + i {\displaystyle 6k+i} for a positive integer k {\displaystyle k} and i ∈ { 0 , 1 , 2 , 3 , 4 , 5 } {\displaystyle i\in \{0,1,2,3,4,5\}} . Since 2 divides 6 k , 6 k + 2 {\displaystyle 6k,6k+2} , and 6 k + 4 {\displaystyle 6k+4} , and 3 divides 6 k {\displaystyle 6k} and 6 k + 3 {\displaystyle 6k+3} ,

5328-568: Is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm. This hypothesis is called the Cobham–Edmonds thesis . The complexity class NP , on the other hand, contains many problems that people would like to solve efficiently, but for which no efficient algorithm is known, such as the Boolean satisfiability problem , the Hamiltonian path problem and

5439-902: Is possible that P = P S P A C E {\displaystyle P=PSPACE} . If P {\displaystyle P} is not equal to N P {\displaystyle NP} , then P {\displaystyle P} is not equal to P S P A C E {\displaystyle PSPACE} either. Since there are many known complexity classes between P {\displaystyle P} and P S P A C E {\displaystyle PSPACE} , such as R P {\displaystyle RP} , B P P {\displaystyle BPP} , P P {\displaystyle PP} , B Q P {\displaystyle BQP} , M A {\displaystyle MA} , P H {\displaystyle PH} , etc., it

5550-444: Is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory. Along the same lines, c o - N P {\displaystyle co{\text{-}}NP} is the class containing the complement problems (i.e. problems with the yes / no answers reversed) of N P {\displaystyle NP} problems. It

5661-428: Is prime. For a last example, consider 221. One has 14 < 221 < 15 {\displaystyle 14<{\sqrt {221}}<15} , and the primes ≤ 221 {\displaystyle \leq {\sqrt {221}}} are 2, 3, 5, 7, 11, and 13. Upon checking each, one discovers that 221 / 13 = 17 {\displaystyle 221/13=17} , proving that 221

SECTION 50

#1733085330713

5772-423: Is probably prime. It has been shown that there are no counterexamples for n < 2 64 {\displaystyle <2^{64}} . Leonard Adleman and Ming-Deh Huang presented an errorless (but expected polynomial-time) variant of the elliptic curve primality test . Unlike the other probabilistic tests, this algorithm produces a primality certificate , and thus can be used to prove that

5883-427: Is said to reject the input. An example of a decision problem is the following. The input is an arbitrary graph . The problem consists in deciding whether the given graph is connected or not. The formal language associated with this decision problem is then the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings. A function problem

5994-595: Is sufficient. For example, consider the number 100, whose divisors are these numbers: When all possible divisors up to n {\displaystyle n} are tested, some divisors will be discovered twice . To observe this, consider the list of divisor pairs of 100: Products past 10 × 10 {\displaystyle 10\times 10} are the reverse of products that appeared earlier. For example, 5 × 20 {\displaystyle 5\times 20} and 20 × 5 {\displaystyle 20\times 5} are

6105-449: Is that the machines operate deterministically . However, some computational problems are easier to analyze in terms of more unusual resources. For example, a non-deterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The non-deterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of

6216-494: Is the general number field sieve , which takes time O ( e ( 64 9 3 ) ( log ⁡ n ) 3 ( log ⁡ log ⁡ n ) 2 3 ) {\displaystyle O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log n)}}{\sqrt[{3}]{(\log \log n)^{2}}}})} to factor an odd integer n {\displaystyle n} . However,

6327-458: Is the class of all decision problems. For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on (say) computation time indeed defines a bigger set of problems. In particular, although DTIME( n {\displaystyle n} ) is contained in DTIME( n 2 {\displaystyle n^{2}} ), it would be interesting to know if

6438-478: Is the computational problem of determining the prime factorization of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a prime factor less than k {\displaystyle k} . No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the RSA algorithm. The integer factorization problem

6549-403: Is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called randomized algorithms . A non-deterministic Turing machine

6660-400: Is the set of NP-hard problems. If a problem X {\displaystyle X} is in C {\displaystyle C} and hard for C {\displaystyle C} , then X {\displaystyle X} is said to be complete for C {\displaystyle C} . This means that X {\displaystyle X} is

6771-415: Is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine M {\displaystyle M} is said to operate within time f ( n ) {\displaystyle f(n)} if the time required by M {\displaystyle M} on each input of length n {\displaystyle n}

SECTION 60

#1733085330713

6882-473: Is usually prime. But here is a counterexample: if n = 341 and a = 2, then even though 341 = 11·31 is composite. In fact, 341 is the smallest pseudoprime base 2 (see Figure 1 of ). There are only 21853 pseudoprimes base 2 that are less than 2.5 × 10 (see page 1005 of ). This means that, for n up to 2.5 × 10 , if 2 (modulo n ) equals 1, then n is prime, unless n is one of these 21853 pseudoprimes. Some composite numbers ( Carmichael numbers ) have

6993-400: Is whether the graph isomorphism problem is in P {\displaystyle P} , N P {\displaystyle NP} -complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete. If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. Since it is widely believed that

7104-597: The Fundamental Theorem of Arithmetic . Therefore the algorithm need only search for prime divisors less than or equal to n {\displaystyle {\sqrt {n}}} . For another example, consider how this algorithm determines the primality of 17. One has 4 < 17 < 5 {\displaystyle 4<{\sqrt {17}}<5} , and the only primes ≤ 17 {\displaystyle \leq {\sqrt {17}}} are 2 and 3. Neither divides 17, proving that 17

7215-479: The big O notation , which hides constant factors and smaller terms. This makes the bounds independent of the specific details of the computational model used. For instance, if T ( n ) = 7 n 2 + 15 n + 40 {\displaystyle T(n)=7n^{2}+15n+40} , in big O notation one would write T ( n ) = O ( n 2 ) {\displaystyle T(n)=O(n^{2})} . A complexity class

7326-482: The discrete logarithm problem and the integer factorization problem are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in P {\displaystyle P} or to be N P {\displaystyle NP} -complete. The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic . An important unsolved problem in complexity theory

7437-426: The graph isomorphism problem , and decision versions of factoring and the discrete logarithm . Under the exponential time hypothesis , there exist natural problems that require quasi-polynomial time , and can be solved in that time, including finding a large disjoint set of unit disks from a given set of disks in the hyperbolic plane , and finding a graph with few vertices that is not an induced subgraph of

7548-442: The instance is a particular input to the problem, and the solution is the output corresponding to the given input. To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the travelling salesman problem : Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance

7659-611: The vertex cover problem . Since deterministic Turing machines are special non-deterministic Turing machines, it is easily observed that each problem in P is also member of the class NP. The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution. If the answer is yes, many important problems can be shown to have more efficient solutions. These include various types of integer programming problems in operations research , many problems in logistics , protein structure prediction in biology , and

7770-512: The Adleman–Huang algorithm reduced the complexity to ⁠ Z P P = R P ∩ c o R P {\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}} ⁠ , which superseded Pratt's result. The Adleman–Pomerance–Rumely primality test from 1983 put PRIMES in QP ( quasi-polynomial time ), which is not known to be comparable with

7881-547: The Solovay–Strassen test does not. This is because 1905 is an Euler pseudoprime base 2 but not a strong pseudoprime base 2 (this is illustrated in Figure 1 of PSW ). The Miller–Rabin and the Solovay–Strassen primality tests are simple and are much faster than other general primality tests. One method of improving efficiency further in some cases is the Frobenius pseudoprimality test ; a round of this test takes about three times as long as

7992-780: The ability to find formal proofs of pure mathematics theorems. The P versus NP problem is one of the Millennium Prize Problems proposed by the Clay Mathematics Institute . There is a US$ 1,000,000 prize for resolving the problem. It was shown by Ladner that if P ≠ N P {\displaystyle P\neq NP} then there exist problems in N P {\displaystyle NP} that are neither in P {\displaystyle P} nor N P {\displaystyle NP} -complete. Such problems are called NP-intermediate problems. The graph isomorphism problem ,

8103-476: The amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity ), the number of gates in a circuit (used in circuit complexity ) and the number of processors (used in parallel computing ). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem , one of

8214-507: The basis for most separation results of complexity classes. For instance, the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us that L is strictly contained in PSPACE. Many complexity classes are defined using the concept of a reduction. A reduction is a transformation of one problem into another problem. It captures the informal notion of

8325-444: The basis for the complexity class P , which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP . 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: Logarithmic-space classes do not account for

8436-452: The basis of many more practical methods. These are tests that seem to work well in practice, but are unproven and therefore are not, technically speaking, algorithms at all. The Fermat test and the Fibonacci test are simple examples, and they are very effective when combined. John Selfridge has conjectured that if p is an odd number, and p ≡ ±2 (mod 5), then p will be prime if both of

8547-403: The beginning of the 20th century, it was shown that a corollary of Fermat's little theorem could be used to test for primality. This resulted in the Pocklington primality test . However, as this test requires a partial factorization of n  − 1 the running time was still quite slow in the worst case. The first deterministic primality test significantly faster than the naive methods

8658-507: The best known quantum algorithm for this problem, Shor's algorithm , does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes. Many known complexity classes are suspected to be unequal, but this has not been proved. For instance P ⊆ N P ⊆ P P ⊆ P S P A C E {\displaystyle P\subseteq NP\subseteq PP\subseteq PSPACE} , but it

8769-590: The chosen machine model. For instance, the language { x x ∣ x  is any binary string } {\displaystyle \{xx\mid x{\text{ is any binary string}}\}} can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" ( Goldreich 2008 , Chapter 1.2). This forms

8880-512: The classes mentioned above. Because of its tractability in practice, polynomial-time algorithms assuming the Riemann hypothesis, and other similar evidence, it was long suspected but not proven that primality could be solved in polynomial time. The existence of the AKS primality test finally settled this long-standing question and placed PRIMES in P . However, PRIMES is not known to be P-complete , and it

8991-441: The discussion abstract enough to be independent of the choice of encoding. This can be achieved by ensuring that different representations can be transformed into each other efficiently. Decision problems are one of the central objects of study in computational complexity theory. A decision problem is a type of computational problem where the answer is either yes or no (alternatively, 1 or 0). A decision problem can be viewed as

9102-612: The division leaves no remainder ). If so, then n {\displaystyle n} is composite . Otherwise, it is prime. For any divisor p ≥ n {\displaystyle p\geq {\sqrt {n}}} , there must be another divisor n / p ≤ n {\displaystyle n/p\leq {\sqrt {n}}} , and a prime divisor q {\displaystyle q} of n / p {\displaystyle n/p} , and therefore looking for prime divisors at most n {\displaystyle {\sqrt {n}}}

9213-469: The following hold: where f k is the k -th Fibonacci number . The first condition is the Fermat primality test using base 2. In general, if p ≡ a (mod x +4), where a is a quadratic non-residue (mod x +4) then p should be prime if the following conditions hold: f ( x ) k is the k -th Fibonacci polynomial at x . Selfridge, Carl Pomerance and Samuel Wagstaff together offer $ 620 for

9324-746: The form 30 k + i {\displaystyle 30k+i} for i ∈ { 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 } {\displaystyle i\in \{1,7,11,13,17,19,23,29\}} . Of course, not all numbers of the form c # ⋅ k + i {\displaystyle c\#\cdot k+i} with i {\displaystyle i} coprime to c # {\displaystyle c\#} are prime. For example, 19 ⋅ 23 = 437 = 210 ⋅ 2 + 17 = 2 ⋅ 7 # + 17 {\displaystyle 19\cdot 23=437=210\cdot 2+17=2\cdot 7\#+17}

9435-658: The form 30 k + i {\displaystyle 30k+i} for i , k {\displaystyle i,k} integers with 0 ≤ i < 30 {\displaystyle 0\leq i<30} . Now, 2 divides 0 , 2 , 4 , … , 28 {\displaystyle 0,2,4,\dots ,28} , 3 divides 0 , 3 , 6 , … , 27 {\displaystyle 0,3,6,\dots ,27} , and 5 divides 0 , 5 , 10 , … , 25 {\displaystyle 0,5,10,\dots ,25} . Thus all prime numbers greater than 30 are of

9546-462: The hardest problem in C {\displaystyle C} . (Since many problems could be equally hard, one might say that X {\displaystyle X} is one of the hardest problems in C {\displaystyle C} .) Thus the class of NP-complete problems contains the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. Because

9657-449: The implementation of these two methods is rather difficult and creates a risk of programming errors, slower but simpler tests are often preferred. In 2002, the first provably unconditional deterministic polynomial time test for primality was invented by Manindra Agrawal , Neeraj Kayal , and Nitin Saxena . The AKS primality test runs in Õ((log  n ) ) (improved to Õ((log  n ) ) in

9768-516: The inclusion is strict. For time and space requirements, the answer to such questions is given by the time and space hierarchy theorems respectively. They are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources. Thus there are pairs of complexity classes such that one is properly included in the other. Having deduced such proper set inclusions, we can proceed to make quantitative statements about how much more additional time or space

9879-417: The latter theory asks what kinds of problems can, in principle, be solved algorithmically. A computational problem can be viewed as an infinite collection of instances together with a set (possibly empty) of solutions for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory,

9990-484: The list in half, also needing O ( n log ⁡ n ) {\displaystyle O(n\log n)} time. To classify the computation time (or similar resources, such as space consumption), it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem. The complexity of an algorithm is usually taken to be its worst-case complexity unless specified otherwise. Analyzing

10101-466: The mathematical models we want to analyze, so that non-deterministic time is a very important resource in analyzing computational problems. For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the deterministic Turing machine is used. The time required by a deterministic Turing machine M {\displaystyle M} on input x {\displaystyle x}

10212-555: The method of reduction, such as Cook reductions, Karp reductions and Levin reductions, and the bound on the complexity of reductions, such as polynomial-time reductions or log-space reductions . The most commonly used reduction is a polynomial-time reduction. This means that the reduction process takes polynomial time. For example, the problem of squaring an integer can be reduced to the problem of multiplying two integers. This means an algorithm for multiplying two integers can be used to square an integer. Indeed, this can be done by giving

10323-522: The number n .) The elliptic curve primality test can be proven to run in O((log ; n ) ), if some conjectures on analytic number theory are true. Similarly, under the extended Riemann hypothesis , the deterministic Miller's test , which forms the basis of the probabilistic Miller–Rabin test, can be proved to run in Õ ((log  n ) ). In practice, this algorithm is slower than the other two for sizes of numbers that can be dealt with at all. Because

10434-510: The odd numbers between 3 and n {\displaystyle {\sqrt {n}}} , since divisibility by an even number implies divisibility by 2. This method can be improved further. Observe that all primes greater than 3 are of the form 6 k + i {\displaystyle 6k+i} for a nonnegative integer k {\displaystyle k} and i ∈ { 1 , 5 } {\displaystyle i\in \{1,5\}} . Indeed, every integer

10545-525: The only possible remainders mod 6 for a prime greater than 3 are 1 and 5. So, a more efficient primality test for n {\displaystyle n} is to test whether n {\displaystyle n} is divisible by 2 or 3, then to check through all numbers of the form 6 k + 1 {\displaystyle 6k+1} and 6 k + 5 {\displaystyle 6k+5} which are ≤ n {\displaystyle \leq {\sqrt {n}}} . This

10656-530: The polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to László Babai and Eugene Luks has run time O ( 2 n log ⁡ n ) {\displaystyle O(2^{\sqrt {n\log n}})} for graphs with n {\displaystyle n} vertices, although some recent work by Babai offers some potentially new perspectives on this. The integer factorization problem

10767-697: The preceding can be applied recursively , giving the Sieve of Eratosthenes . One way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, such as all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes or by an algorithm that tests each incremental m {\displaystyle m} against all known primes ≤ m {\displaystyle \leq {\sqrt {m}}} ). Then, before testing n {\displaystyle n} for primality with

10878-400: The problem P = NP is not solved, being able to reduce a known NP-complete problem, Π 2 {\displaystyle \Pi _{2}} , to another problem, Π 1 {\displaystyle \Pi _{1}} , would indicate that there is no known polynomial-time solution for Π 1 {\displaystyle \Pi _{1}} . This

10989-531: The problem of sorting a list of integers. The worst-case is when the pivot is always the largest or smallest value in the list (so the list is never divided). In this case, the algorithm takes time O ( n 2 {\displaystyle n^{2}} ). If we assume that all possible permutations of the input list are equally likely, the average time taken for sorting is O ( n log ⁡ n ) {\displaystyle O(n\log n)} . The best case occurs when each pivoting divides

11100-621: The property that a is 1 (modulo n ) for every a that is coprime to n . The smallest example is n = 561 = 3·11·17, for which a is 1 (modulo 561) for all a coprime to 561. Nevertheless, the Fermat test is often used if a rapid screening of numbers is needed, for instance in the key generation phase of the RSA public key cryptographic algorithm . The Miller–Rabin primality test and Solovay–Strassen primality test are more sophisticated variants, which detect all composites (once again, this means: for every composite number n , at least 3/4 (Miller–Rabin) or 1/2 (Solovay–Strassen) of numbers

11211-464: The published revision of their paper), which can be further reduced to Õ((log  n ) ) if the Sophie Germain conjecture is true. Subsequently, Lenstra and Pomerance presented a version of the test which runs in time Õ((log  n ) ) unconditionally. Agrawal, Kayal and Saxena suggest a variant of their algorithm which would run in Õ((log  n ) ) if Agrawal's conjecture is true; however,

11322-438: The reverse of each other. Further, that of the two divisors, 5 ≤ 100 = 10 {\displaystyle 5\leq {\sqrt {100}}=10} and 20 ≥ 100 = 10 {\displaystyle 20\geq {\sqrt {100}}=10} . This observation generalizes to all n {\displaystyle n} : all divisor pairs of n {\displaystyle n} contain

11433-581: The same input to both inputs of the multiplication algorithm. Thus we see that squaring is not more difficult than multiplication, since squaring can be reduced to multiplication. This motivates the concept of a problem being hard for a complexity class. A problem X {\displaystyle X} is hard for a class of problems C {\displaystyle C} if every problem in C {\displaystyle C} can be reduced to X {\displaystyle X} . Thus no problem in C {\displaystyle C}

11544-403: The set of problems solvable within time f ( n ) {\displaystyle f(n)} on a deterministic Turing machine is then denoted by DTIME ( f ( n ) {\displaystyle f(n)} ). Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any complexity measure can be viewed as

11655-472: The set {0,1}), and thus the strings are bitstrings . 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 , or by encoding their adjacency lists in binary. Even though some proofs of complexity-theoretic theorems regularly assume some concrete choice of input encoding, one tries to keep

11766-399: The seven Millennium Prize Problems , is part of the field of computational complexity. Closely related fields in theoretical computer science are analysis of algorithms and computability theory . A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve

11877-545: The space required to represent the problem. It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem . Other important complexity classes include BPP , ZPP and RP , which are defined using probabilistic Turing machines ; AC and NC , which are defined using Boolean circuits; and BQP and QMA , which are defined using quantum Turing machines. #P is an important complexity class of counting problems (not decision problems). Classes like IP and AM are defined using Interactive proof systems . ALL

11988-435: The space required, or any measure of complexity) is calculated as a function of the size of the instance. The input size is typically measured in bits. Complexity theory studies how algorithms scale as input size increases. For instance, in the problem of finding whether a graph is connected, how much more time does it take to solve a problem for a graph with 2 n {\displaystyle 2n} vertices compared to

12099-417: The time complexity (or any other complexity measure) of different inputs of the same size. Since some inputs of size n {\displaystyle n} may be faster to solve than others, we define the following complexities: The order from cheap to costly is: Best, average (of discrete uniform distribution ), amortized, worst. For example, the deterministic sorting algorithm quicksort addresses

12210-416: The time taken for a graph with n {\displaystyle n} vertices? If the input size is n {\displaystyle n} , the time taken can be expressed as a function of n {\displaystyle n} . Since the time taken on different inputs of the same size can be different, the worst-case time complexity T ( n ) {\displaystyle T(n)}

12321-411: Was the cyclotomy test ; its runtime can be proven to be O ((log  n ) ), where n is the number to test for primality and c is a constant independent of n . Many further improvements were made, but none could be proven to have polynomial running time. (Running time is measured in terms of the size of the input, which in this case is ~ log  n , that being the number of bits needed to represent

#712287