Friday, June 17, 2005

Implications of the TUMity on the SAT problem/search algorithms

Things, like searching for a cycle etc., can be done in polynomial time when a graph is TUM. What does this mean for a SAT problem? In general, what does it mean for a search algorithm which tries to solve a SAT problem?

No comments: