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.
GLOSSARY
Measures of complexity: Time and space
Time complexity: Measure of how long a computation takes to execute.
Space complexity: Measure of how much storage is required for a
computation.
Kinds of complexity analysis: (a) average case (b) worst case (c) best case
Polynomial time algorithm: An algorithm whose execution time is either
given by a polynomial on the size of the input, or can be bounded by
such a polynomial.
Heapsort complexity: O(n
n
log ) at all times.
Quicksort complexity: O(n
n
log ) time an average, O n
( )
2 time in the worst
case.
Nondeterministic Polynomial time algorithm: One that can be executed in
polynomial time on a non-deterministic machine.
NP problem: How a polynomial-time solution, but an exponential time
solution on a deterministic machine.
TSP: Travelling salesman problem.
REVIEW QUESTIONS
1. What is meant by complexity theory?
2. What do you mean by Time complexity?
3. What do you mean by space complexity?
4. Define order-statistic in complexity theory?
5. Define O-notation (Big O).
6. What do you mean by Polynomial Time algorithms?
7. What do you mean by non-polynomial time algorithms?
240
Theory of Automata, Formal Languages and Computation