A DAG whose vertices are gates of five types:
- AND
- OR
- NOT
- Known input (no incoming edges)
- Unknown input (no incoming edges) One sink of the DAG is the output gate which we want to be true.
Given a boolean circuit, find a truth assignment for the unknown inputs such that output = true, or determine no assignment exists.
- This is a well-defined search problem
- This is a generalization of SAT