Satisfiability problem

Read the full explanation here.

A small example for encoding a Boolean formula into an input string for the ADP program:
Boolean formula: (x1 OR x2) AND (NOT(x2) OR x3)
ADP input: "PP-&-NP"