Skedbooks
←
Automata | Comp. Sc. Engg.

Additional Np Problem

ADDITIONAL NP PROBLEMS: The following problems have a polynomial-time solution, but an exponential-time solution on a deterministic machine. There are literally hundreds of additional examples.

  1. The Travelling Salesman Problem (TSP): A salesman starting in Texas, wants to visit every capital city in the United States, returning to Texas as his last stop. In what order should he visit the capital cities so as to minimize the total distance travelled?
  2. The Hamiltonian Circuit Problem: Every capital city has direct air flights to at least some capital cities. Our intrepid salesman wants to visit all the capitals, and return to his starting point, taking only direct air flights. Can he find a path that lets him do this?
  3. Linear Programming: We have on hand X amount of butter, Y amount of flour, Z eggs etc. We have cookie recipies that use varying amounts of these ingredients. Different kinds of cookies bring different prices. What mix of cookies should we make in order to maximize profits?

NP-COMPLETE PROBLEMS: All the known NP problems have a remarkable characteristic: They are all reducible to one another. What this means is that, given any two NP problems X and Y,

(a) There exists a polynomial-time algorith to restate a problem of type X as a problem of type Y, and

(b) There exists a polynomial-time algorithm to translate a solution to a type Y problem back into a solution for the type X problem.

This is what the “complete” refers to when we talk about NP-complete problems. What this means is that, if anyone ever discovers a polynomial-time algorithm for any of these problems, then there is an easily-derived polynomial-time algorithm for all of them. This leads to the question.

Does P = NP?

No one has ever found a deterministic polynomial-time algorithm for any of these problems (or the hundreds of others like them). However, no one has ever succeeded in proving that no deterministic polynomial time algorithm exists, either. The status for some years now is this: most computer scientists don’t think a polynomial-time algorithm can exist, but no one knows for sure.