My friend was unable to come up with anything that runs in less than exponential time. He wanted to convince his boss that
no one else could have done any better. He went and told the boss this: "Look, this time-tabling problem can be easily (i.e., in polynomial time)
converted into a boolean satisfiability problem. Now, it is well known that boolean satisfiability is an NP-Complete problem (i.e., it is one of 'em
monster problems in class NP). So it is no bloody surprise that I am unable to come up with anything other than an exponential algorithm".
What do you think of my friends' reasoning?
2. Explain why the arguments based on reductions to/from NP-complete problems is needed? Can't we just prove that a problem can't have anything
other than exponential (or polynomial) solution? Do you know of any famous problems that were thought to be exponential for a long time until someone found a polynomial algorithm?
3. Here is a "boolean satisfiability" problem. (If you need background, look at the wikipedia entry: http://en.wikipedia.org/wiki/Boolean_satisfiability_problem )
Propositions: P, Q, R ,
Clauses: P V Q ; ~Q V ~R [~ means "not"]
Explain, for each of the following complete assignments, whether the assignment is a solution to the problem or not:
3.1. P=True, Q=True; R=True
3.2. P=False, Q= False, R=False
3.3 P=True, Q=False, R=True