tag:blogger.com,1999:blog-7830981159451315932.post3116522501789208521..comments2011-05-21T18:35:23.807-07:00Comments on ASU101, Fall 2010 (Rao): Qns on NP-Completeness etcSubbarao Kambhampatihttp://www.blogger.com/profile/08449853328445416609noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-7830981159451315932.post-51227594091426550692010-09-13T12:36:07.739-07:002010-09-13T12:36:07.739-07:001. r must be false for ~r to be true.
So noth Q a...1. r must be false for ~r to be true.<br /><br />So noth Q and P must be false for <br />~q v r and ~p v r to both be true.<br />So p v q will end up false thus it does not work.<br /><br />2.One sat would not seem to be a polynomial. A binomial maybe. <br /><br />3. Yes as another poster has already stated. <br /><br />4. A partial guess. Maybe if converted to binary numbers. Compare the left most digits one at a time in same power position.<br />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.<br />If not equal then:<br />If ~a V b is true a is less than b.<br />If false a is greater than b.<br /><br /><br />This is for binary numbers a and b.Erichttps://www.blogger.com/profile/14154515279392473743noreply@blogger.comtag:blogger.com,1999:blog-7830981159451315932.post-78822397304052469982010-09-12T04:39:40.874-07:002010-09-12T04:39:40.874-07:001. Very sound reasoning. If a problem is converted...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.<br /><br />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.<br /><br />3. true and true ; false and false not satisfied<br /><br />false and false ; true and true not satisfied<br /><br />true and false ; true and false is validDamion Whitehttps://www.blogger.com/profile/01656850468411481287noreply@blogger.comtag:blogger.com,1999:blog-7830981159451315932.post-48120931363365956032010-09-09T20:27:31.844-07:002010-09-09T20:27:31.844-07:001. I think the reasoning was correct, but would ha...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.<br /><br />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.<br /><br />3. I don't get it.Colbyhttps://www.blogger.com/profile/17680688766930059844noreply@blogger.comtag:blogger.com,1999:blog-7830981159451315932.post-59897765029357265362010-09-09T13:00:34.218-07:002010-09-09T13:00:34.218-07:001. Is Boolean satisfiability basically the process...1. Is Boolean satisfiability basically the process of trying to find solutions that are...well...solutions? 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. <br /><br />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...<br /><br />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.Regino Floreshttps://www.blogger.com/profile/18128567265026687375noreply@blogger.comtag:blogger.com,1999:blog-7830981159451315932.post-50939478355425512010-09-06T12:11:13.107-07:002010-09-06T12:11:13.107-07:001. I think he may be correct. If you can show th...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.<br /><br />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.<br /><br />3.1 (T)V(T) ; (F)V(F) NO<br />3.2 (F)V(F) ; (T)V(T) NO<br />3.3 (T)V(F) ; (T)V(F) YESNicolas Foxhttps://www.blogger.com/profile/07298811505196759233noreply@blogger.com