TQBF

Translingual

Etymology

From English True (or totally) quantified Boolean formula.

Symbol

TQBF

1. (computing theory) The decision problem of, given a Boolean function f on n variables, deciding whether the following formula is satisfiable:

   $\exists x_{1}\forall x_{2}\exists x_{3}...Q_{n}x_{n}f(x_{1},x_{2},x_{3},...,x_{n})$

   Where $Q_{n}$ is $\forall$ if n is even and $\exists$ if n is odd.

See also

• SAT