>>21818880

> POCO doesn't have shit to do with the Boolean satisfiability problem you stupid LARP, oh god

Let me put this in very simple words, for a simpleton faggot like you

In computational complexity theory, the quantified Boolean formula problem (QBF) is a generalization of the Boolean satisfiability problem in which both existential quantifiers and universal quantifiers can be applied to each variable - which represents a subset of the poco protocol in the cardinatlity of workers and machine verified tasks. Put another way, POCO asks whether a quantified sentential form over a set of Boolean variables is true or false. For example, the following is an instance of QBF:

POCO-QBF is the canonical complete problem for PSPACE, the class of problems solvable by a deterministic or nondeterministic Turing machine in polynomial space and unlimited time. Given the formula in the form of an abstract syntax tree, the problem can be solved easily by a set of mutually recursive procedures which evaluate the formula. Such an algorithm uses space proportional to the height of the tree, which is linear in the worst case, but uses time exponential in the number of quantifiers.

Provided that MA ⊊ PSPACE, which is widely believed, QBF cannot be solved, nor can a given solution even be verified, in either deterministic or probabilistic polynomial time (in fact, unlike the satisfiability problem, there's no known way to specify a solution succinctly). It can be solved using an alternating Turing machine in linear time, since AP = PSPACE, where AP is the class of problems alternating machines can solve in polynomial time.

When the seminal result IP = PSPACE was shown (see interactive proof system), it was done by exhibiting an interactive proof system that could solve QBF by solving a particular arithmetization of the problem.