True quantified Boolean formula
ID: true-quantified-boolean-formula
A True Quantified Boolean Formula (TQBF) is a specific type of Boolean formula that is a decision problem in computational complexity theory. It extends the concept of Boolean formulas by incorporating quantifiers (universal and existential) over the variables involved. ### Definition: A TQBF is a prenex normal form Boolean formula that can be expressed as follows: - It consists of a sequence of quantifiers followed by a propositional formula.
New to topics? Read the docs here!