Monday, 29 June 2009

To Go or not To Go !!!!

This is the question !!!
I usually don't like this kind of decisions.. It's not easy to give your yes/no answer.
Well.. let me see how hard it is !!
Mmm... I think this problem ( let's call " offerProblem" ) is NP-Complete problem. So let's make one silly proof :)
1) The problem is NP: you can guess a set of conditions(that's nondeterminstic) and check ( in polynomial time ) if it will make you happy and satisfied.
2) Now let's reduce an NPC problem (SAT) to our problem (offer): The reduction is very trivial indeed, or it's nothing, you have your satisfaction formula.. the offer will assign values to your variables.. if you have a satisfying assignment, then you have your answer
So we have an NP-Complete problem here:)
Very silly, huh ?! :)

Anyway.. It's still hard

4 comments:

ست المرتفعات said...

طبعا مفهمتش حاجة من الاثبات العبقرى بتاعك دا بس اقدر اقولك

to go
فولو يور تااااااكيف

ولازم تتأكدى ياهانم من أن التكيفف ضمان 3 سنين ع الاقل


ياله صباحك سكر

Unknown said...

الاثبات ده للمشكلة بوجه عام
خدمه للأجيال القادمه يعني :)
و صباحك أحلي من السكر
:)

ES said...

Ya ragel :) , yes it`s avery traivial case , but i have another solution if hanshed shwyh el NP = NPC then NPC=SAT loool ...
w da3e el 7`lk lel 7`lek ba2a :)

Unknown said...

ايه العبقريه دي يا سو :)
solving NPC in polynomial time --> NP= P
bravo :)