2
$\begingroup$

My Question is, what is meant with smallest number N. Does it mean I should try every possible constellation of the n variables and put each one of them into the formula φ and then use 3Sat on that? Then it would be 2$^{n}$? Is that meant?

$\endgroup$

2 Answers 2

2
$\begingroup$

You could try every possible assignment but you can do better.

Think about how you solve this problem recursively: Given bits $x_0^* \ldots x_i^*$ and we have that $\varphi(x_0^*, \ldots x_i^*, x_{i+1} \ldots x_n)$ is satisfiable for some $x_{i+1} \ldots x_n$. Now you just need to determine whether $\varphi(x_0^*, \ldots x_i^*, x_{i+1}^*, x_{i+2} \ldots x_n)$ is satisfiable if you fix $x_{i+1}^*=1$ or $x_{i+1}^*=0$, which gives you bits $x_0^* \ldots x_{i+1}^*$.

Can you take it from here?

$\endgroup$
2
  • $\begingroup$ So I start with x0* and set it to 1 and check with the algorithm if it still satisfies, if not I will check x0*=1, then I continue with x1. This means I find a solution after 2n. But is the second check required when we know that the formula is satisfiable? Doesn't that mean if not 1 satisfies then 0 has to satisfy the formular. $\endgroup$
    – OttoFran
    Dec 7, 2021 at 18:27
  • $\begingroup$ @OttoFran Yes, you technically only need n+1 queries. See also: cs.stackexchange.com/questions/29482/… $\endgroup$
    – idmean
    Dec 7, 2021 at 19:42
2
$\begingroup$

You are given a machine which solves SAT. You can give it any formula $\varphi$, pay a fee of \$1, and then it immediately tells you whether $\varphi$ is satisfiable or not.

Using this machine, you want to find a satisfying assignment for a formula $\psi$ on $n$ variables which is promised to be satisfiable. How much would it cost you, using the optimal strategy? (You're trying to minimize the cost, which is the same as minimizing the number of invocations of the machine.)

$\endgroup$
4
  • $\begingroup$ SAT only tells me if it is satisfiable, so how should I get a satisfiable assignment out of that? Thats why I thought I have to try all possible combinations for the n variables of φ and then use SAT on that. That would be 2$^{n}$ combinations. Is that correct? $\endgroup$
    – OttoFran
    Dec 7, 2021 at 14:49
  • 1
    $\begingroup$ You can do a lot better. This is your question, though, so I don’t want to ruin it by spelling out the answer. $\endgroup$ Dec 7, 2021 at 14:50
  • $\begingroup$ I don't get it can you give me at least a small hint. (For me its unclear how i can check with a general SAT check if an explicit assignment is satisfiable) $\endgroup$
    – OttoFran
    Dec 7, 2021 at 15:37
  • $\begingroup$ It’s not supposed to be obvious or immediate. It requires an idea. $\endgroup$ Dec 7, 2021 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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