Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/#!/StackCompSci/status/275733503939837953
edited tags
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393
edited tags; edited title
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393

How is verifying whether an assignment satisfies a boolean formula $\in P$possible in polynomial time?

Source Link
David Faux
David Faux
  • 1.6k
  • 5
  • 22
  • 28

How is verifying whether an assignment satisfies a boolean formula $\in P$?

How can I prove that I can verify whether a boolean assignment of variables $a$ satisfies some boolean formmula $\phi$ in polynomial time?

I know that we can just plug the boolean assignment into the formula, but this seems to be a very high-level description, and I am not sure that it is a reliable one since we must simplify the formula.