NP-Completeness Theory
The topics we discussed so far are positive results:
Given a problem, how to design efficient algorithms for solving it.
NP-Completeness (NPC for sort) Theory is negative results.
It studies the problems that cannot be solved efficiently.
Why we study negative results?
In some sense, the negative results are more important than positive
results:
The negative result may say that a given problem Q cannot be solved in
polynomial time.
Without knowing it, you will have to keep trying to find polynomial time
algorithm for solving Q. All your efforts are doomed!
NPC Theory tells you when to give up: Don’t waste your time on
something that is impossible.
c
Xin He (University at Buffalo) CSE 431/531 Algorithm Analysis and Design 2 / 110
What is Computation?
Computers are powerful, and getting more and more powerful every day.
But there are limitations: There are certain tasks that they cannot do!
We have to be more precise: What is Computation?
The following quotation is from Electronics Technology and Computer
Science, 1940 - 1975: A Coevolution, by Computer Science historian Paul
Ceruzzi, published in Annals Hist. Comput. Vol 10, 1989 pp. 257-275:
Quotation
That is the definition of computer science as the study of algorithms -
effective procedures - and their implementation by programming languages
on digital computer hardware. Implied in this definition is the notion that the
algorithm is as fundamental to computing as Newton’s Law of Motion to
Physics; thus Computer Science is a true science because it is concerned
with discovering natural laws about algorithms, ....
c
Xin He (University at Buffalo) CSE 431/531 Algorithm Analysis and Design 3 / 110
