Talk:True quantified Boolean formula

Latest comment: 3 years ago by Duckmather in topic Rated quality and importance

The example given at the beginning is somewhat unsuitable because the boolean part is already valid, and therfore true for any combination of Quantifiers 134.2.102.191 (talk) 14:29, 6 April 2009 (UTC)Reply

and

edit

It would be nice to have a comparison with   and   (  and  , respectively) too. 129.240.71.6 (talk) 16:40, 28 March 2011 (UTC)Reply

Can you please clarify what   mean? (Are you referring to intersection and union in set theory, to meet and join in lattice theory, or something else entirely?) Also, I think that it's safe to assume that article readers here know what existential and universal quantifiers are, or read the linked articles on each if they don't. Duckmather (talk) 21:45, 8 April 2021 (UTC)Reply

Miscellany addition

edit

Quantified monotone boolean formulas are linearly decidable. Just plug in True for existentially quantified variables, and False for universally quantified variables, then evaluate.

Additionally, the number of valid quantifications of a boolean formula is equal to the number of satisfying assignments of the boolean formula. (i.e. #P=#PSpace). 24.33.70.144 (talk) 21:24, 1 March 2014 (UTC)Daniel PehoushekReply

This article is not self-contained.

edit

There is no mention of MA (Merlyn/Arthur) before the mention in the paragraph starting:

Provided that MA ⊊ PSPACE, ...

What means that?

I am not expert in Complexity Theory, please can someone rewrite this article in a self contained style. State what is the problem, what has been discovered to build QBF and in what extent can them be solved in practice. What problems remain to be solved. And a schema to guide the reader into this subject.

Rated quality and importance

edit

I rated this article as C-class for quality (the only reason it's not B-class is because of the weird "QBF solvers/Naïve" section, which is probably original research, and also the language is not super accessible to the general public). I also rated this article as Mid-importance, similarly to Boolean satisfiability problem, because TQBF solving is both theoretically important and practically significant. Please review the ratings; thanks. Duckmather (talk) 21:57, 8 April 2021 (UTC)Reply