NP-complete Problems

Let n be the number of inputs. An algorithm exhibits exponential growth if the execution time is proportional to 2n.

NP-complete problems are a class of problems that exhibit exponential growth in all current algorithms.

Previous slide

Next slide

Back to first slide

View graphic version