Skip to main content
3 of 3
edited tags
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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

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.

David Faux
  • 1.6k
  • 5
  • 22
  • 28