Oracle machine and boolean formula - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-22T07:57:55Z https://cs.stackexchange.com/feeds/question/66697 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/66697 0 Oracle machine and boolean formula marka_17 https://cs.stackexchange.com/users/59895 2016-11-30T10:07:45Z 2016-11-30T10:07:45Z <p>Let we have oracle machine. Oracle get boolean formula and answer OK if this formula is feasible. How to explain that we can find satisfying assignment for any formula for polynomial time.</p> <p>I have аn idea, but I'm not sure it is right.</p> <p>Let we have formula $~f: \{0, 1\}^n \to \{0, 1\}$ with $n$ parameter and oracle $\Theta$. And we know that $\Theta(f) = 1$, i.e $f$ is feasible. Then let's check following : if $\Theta (f(1, \dots)) = 1$ then go on to find satisfying assignment i.e check value of $\Theta (f(1, 1, \dots))$ or $\Theta (f(1, 0, \dots))$ else then $\Theta (f(1, \dots)) = 0$ and we also go on to find assignment in same way. Thus, we probably can find satisfying assignment, but I'm not sure. Am I right? If not, could you give me any tips?</p>