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.

I have аn idea, but I'm not sure it is right.

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?

  • 2
    $\begingroup$ If you're not sure whether your idea works, why not try it out in full? You don't need us for that. $\endgroup$ – Yuval Filmus Nov 30 '16 at 10:13
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Dec 3 '16 at 1:35

Your Answer

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

Browse other questions tagged or ask your own question.