Traveling sales person problem
Solve problems which are NP hard – and they can’t be solved in polynomial time.
P versus NP problem: full polynomial versus nondeterministic polynomial problem
A P problem is one that can be solved in “polynomial time,” which means that an algorithm exists for its solution such that the number of steps in the algorithm is bounded by a polynomial function of n, where n corresponds to the length of the input for the problem. Thus, P problems are said to be easy, or tractable. A problem is called NP if its solution can be guessed and verified in polynomial time, and nondeterministic means that no particular rule is followed to make the guess.
P Problem Examples
- DIV(x, y) = (q, r) such that x = y · q + r where r < y. The remainder r is also denoted x mod y.
- GCD(x, y) is dened as the largest z such that z|x and z|y. It can be computed in polynomial time using Euclid’s algorithm.
- exponentiation: EXP(x, y) = x y
- modular exponentiation: MODEXP(x, y, z) = x y mod z
Problems believed to not be in P
Computational problems which are not solvable in poynomial time are said to be intractable. Here are some examples.
- A problem provably not in P?
- The complexity class NP is the class of decision problems (yes/no answer) or languages that have short proofs of membership. More formally: L ∈ NP if there exists a polynomial time verier V and a polynomial q such that
x ∈ L ⇐⇒ ∃w : |w| ≤ q(kxk) , V (x, w) = 1.
The string w is the witness for x.
Example: SAT
NP-complete problems are the hardest problems in NP
- Satisfiability, Travelling Salesman Problem, and Graph 3-Coloring.
- Linear programming problems are NP
- If an NP-complete problem were solvable in polynomial time, then every NP problem would be solvable in polynomial time.
- P <> NP widely believed (but still unproven).
- Integer Factorization: given a composite number N, nd a non-trivial (=other than 1 and N) factor of N. Neither known to be in P nor NP-complete.
- Some algorithms:
- exhaustive search / trial division
- quadratic sieve: this is the best provable algorithm, it runs in time roughly 2 √ kNk
- number field sieve: the unproven time bound for this algorithm is roughly 2 √3 kNk
- So far, there is no known polynomial-time algorithm.
TSP is a NP-hard combinatorial graph problem:
- NP-hard – it can’t be solved in the polynomial time and it’s easy to evaluate given solution.
- Combinatorial, since your answer is a subset from the set of discrete elements (cities).
- Graph – your map can be represented as a graph.
This is an important problem, since it or its variations may be used in many applications such as:
- Logistics (Delivery optimization, route planning etc.)
- Warehouses (Item picking optimization)
- Transportation (Vehicle routing, e.g. bus routing)
- Manufacturing (Drilling holes in circuit boards)
- X-Ray crystallography
- Genome sequencing
- Many, many others