1
$\begingroup$

What would be one good daily life example of SAT problem? I've thought about this one: The problem of placing a bunch of different kinds of glasses in a shared cabinet in such a way that some constraints would be satisfied, such as putting the longer ones in the back of the shorter ones so it will be easier to take them when we need. Is it a good one, or can you think of any other better one?

$\endgroup$
1
$\begingroup$

SAT problems are decision problems that can be categorised as NPC. This informally means although there has not been any solution that can solve these problem in the polynomial order, the solutions of such problems can be satisfied in $O(n^c)$.

About your question, first, you should see your problem has exponential space and cannot be solved in polynomial order; after that, you have to investigate whether its solutions can be satisfied in polynomial time or not. An easy way to model this is to consider the boolean table and an expression to satisfy. Your problem can be considered as the boolean equation and different possibilities of variables can be possible solutions that you may want to verify.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.