A Boolean formula is an expression written with , , and . For example, . Write the language of satisfiable expressions
NP-Complete
Info
is NP-complete.
Clearly , as a nondeterministic Turing machine can guess an assignment to check for satisfiability. Now let with polytime verifier Turing Machine that terminates in . A tableau for with input is an table, where rows represent configurations. Furthermore, assume each configuration is wrapped with .
Let , be the state and tape alphabet of , and . We write the value at in the tableau as . For each , set a variable to if .
Cell Constraint
We require that each cell has exactly one assignment from our variables. This is represented as follows.
Start / End Constraint
We want the first configuration to correspond to the input . This explicitly specifies start state, input, trailing spaces, and boundary character .
Additionally, we require that the automata eventually hits an accept state.
Move Constraint
Within each configuration, there is only a single cell containing a state. The cell to its right represents the tape location of the Turing machine at that step. Suppose . For , the following are valid windows.
The window refers to a region where is the upper central cell. Write as the set of valid windows.
To enforce these transitions, we write the following rule
Analysis
The final boolean formula is given by . There are variables and components in , thus this gives polynomial reduction of any NP problem to some boolean satisfiability instance.
