This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

???

This article has not yet received a rating on Wikipedia's content assessment scale.

???

This article has not yet received a rating on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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]

$\bigvee$ and $\bigwedge$

It would be nice to have a comparison with $\bigvee _{x\in X}$ and $\bigwedge _{x\in X}$ ( $\exists x\in X$ and $\forall x\in X$ , respectively) too. 129.240.71.6 (talk) 16:40, 28 March 2011 (UTC)[reply]

Miscellany addition

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 Pehoushek[reply]

This article is not self-contained.

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.

SPACE complexity

Stating "Thus, this algorithm uses O(n + log n) = O(n) space. This makes the TQBF language part of the PSPACE complexity class." is misleading or even wrong. The algorithm actually uses polynomial space (in the number of variables). If it was O(n), PSPACE would be equal to linear space LIN, since the problem is complete for PSPACE. This is obviously not true... The problem most likely occurred since the problem can be solved in non-deterministic linear space (by just running the given algorithm non-deterministically), so it is in non-deterministic linear space NLIN.

⋁ {\displaystyle \bigvee } and ⋀ {\displaystyle \bigwedge }

Miscellany addition

This article is not self-contained.

SPACE complexity

$\bigvee$ and $\bigwedge$