Saturday, September 4, 2010

Qns on NP-Completeness etc

1. My friend was asked by his boss to come up with an efficient algorithm for a time-tabling problem for the company.
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: )

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



  1. 1. I think he may be correct. If you can show that the problem can only be done in exponential time, using boolean satisfiability, then the problem would be near impossible to solve.

    2. The ability to do this is necessary to understand what kinds of problems we can tackle. I don't think any problems have been changed from exponential to polynomial, much as there have not been any proofs for P=NP.

    3.1 (T)V(T) ; (F)V(F) NO
    3.2 (F)V(F) ; (T)V(T) NO
    3.3 (T)V(F) ; (T)V(F) YES

  2. 1. Is Boolean satisfiability basically the process of trying to find solutions that That concept is pretty confusing to me. But if that's true and your friend has proved it like that...then I guess there's no way to prove that the problem isn't impossible.

    2. Isn't doing that kind of like giving up though? If we can find a way to turn an impossible problem into a do-able one, then I'm sure we can go somewhere from there. It kind of reminds me of a quote tat had to do with true failure...

    3. I don't understand what this question is asking nor how it can be solved. After looking at the answer that Nicolas gave, I think I have an idea of how to go about the solution but I don't understand exactly what the question is asking.

  3. 1. I think the reasoning was correct, but would have to be backed by substantil evidence to prove it cannot be solved in exponential time.

    2. Being able to do this is very important to the success of a business, because you need to know if a problem will take too long to solve and when to move on.

    3. I don't get it.

  4. 1. Very sound reasoning. If a problem is converted into an NP-complete class problem, even if proving that can be done in polynomial time, reducing it to a NP-complete problem means there is a very likely chance that it is unsolvable.

    2. If I could prove that p was indeed = to np, I wouldn't need this class I think cause I would be a millionaire. If a solution is hard to find on a given problem, it is important to know if it can be reduced to an NP-complete class problem, because you could be wasting your time, like Colby said, if it's for a business and there may not be a polynomial time solution.

    3. true and true ; false and false not satisfied

    false and false ; true and true not satisfied

    true and false ; true and false is valid

  5. 1. r must be false for ~r to be true.

    So noth Q and P must be false for
    ~q v r and ~p v r to both be true.
    So p v q will end up false thus it does not work.

    2.One sat would not seem to be a polynomial. A binomial maybe.

    3. Yes as another poster has already stated.

    4. A partial guess. Maybe if converted to binary numbers. Compare the left most digits one at a time in same power position.
    if a and b or ~a and ~b are true they are equal. Go right one position if there is another if not numbers are equal.
    If not equal then:
    If ~a V b is true a is less than b.
    If false a is greater than b.

    This is for binary numbers a and b.


Note: Only a member of this blog may post a comment.