Np-Hard and Np-Completeness Essay

1400 WordsApr 21, 20136 Pages
N P-Hard and N P-Complete Problems Basic concepts • Solvability of algorithms – There are algorithms for which there is no known solution, for example, Turing’s Halting Problem ∗ Decision problem ∗ Given an arbitrary deterministic algorithm A and a finite input I ∗ Will A with input I ever terminate, or enter an infinite loop? – Halting problem cannot be solved by any computer, no matter how much time is provided ∗ In algorithmic terms, there is no algorithm of any complexity to solve this problem • Efficient algorithms – Efficiency measured in terms of speed – For some problems, there is no known efficient solution – Distinction between problems that can be solved in polynomial time and problems for which no polynomial time algorithm is known • Problems classified to belong to one of the two groups 1. Problems with solution times bound by a polynomial of a small degree – Most searching and sorting algorithms – Also called tractable algorithms 2. Problems with best known algorithms not bound by a polynomial – – – – Hard, or intractable, problems Traveling salesperson (O(n2 2n )), knapsack (O(2n/2 )) None of the problems in this group has been solved by any polynomial time algorithm N P-complete problems ∗ No efficient algorithm for an N P-complete problem has ever been found; but nobody has been able to prove that such as algorithm does not exist • Theory of N P-completeness – Show that many of the problems with no polynomial time algorithms are computationally related – The group of problems is further subdivided into two classes N P-complete. A problem that is N P-complete can be solved in polynomial time iff all other N P-complete problems can also be solved in polynomial time N P-hard. If an N P-hard problem can be solved in polynomial time then all N P-complete problems can also be solved in polynomial time – All N P-complete problems are N P-hard but some N P-hard

More about Np-Hard and Np-Completeness Essay

Open Document