Re: Two-step Non-deterministic Process for Solving NP Problems
- From: "Radosław Hofman" <radekh@xxxxxxxxx>
- Date: Mon, 16 Apr 2007 08:00:51 +0200
Hey,
Yes, you are right.
But yet you have to remember that if your randomly-generated set returns
FALSE then you know only that you haven't found solution "yet". If you try
to solve SAT problem (5 from your list) for instance: (a or b) and (not a or
not b) and (a or not b) and (not a or b) you have to check 2^v assignements.
That is why building guess and check algorithms you have to "remember" what
combinations you have generated or use such way of generation to be sure
that you cover all possibilities. Answer NO to problem question requires in
worst case O(combinations)=O(2^v) for SAT.
Cheers,
Radek Hofman
.
- References:
- Prev by Date: Re: My LP Formulation of the TSP: Conclusions
- Next by Date: Re: How to prove "Cfls are not closed under shuffling"
- Previous by thread: Two-step Non-deterministic Process for Solving NP Problems
- Next by thread: Can this be solved in polynomial time?
- Index(es):
