TQBF問題
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/08/29 04:56 UTC 版)
計算複雑性理論において、言語TQBFは量化された真のブール式からなる形式言語である。(完全に)量化されたブール式とは、すべての変数が存在量化子や全称量化子を用いて式の先頭で量化(束縛)された限定命題論理の式である。自由変数が存在しないため、そのような式は真あるいは偽と同値である。もし真と同値ならば、その式は言語TQBFの要素である。この言語はQSAT(量化されたSAT, Quantified SAT)としても知られている。
- ^ M. Garey and D. Johnson (1979). en:Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, California. ISBN 0-7167-1045-5.
- ^ A. Chandra, D. Kozen, and L. Stockmeyer (1981). “Alternation”. Journal of the ACM 28 (1): 114–133. doi:10.1145/322234.322243 .
- ^ Adi Shamir (1992). “Ip = Pspace”. Journal of the ACM 39 (4): 869–877. doi:10.1145/146585.146609 .
- 1 TQBF問題とは
- 2 TQBF問題の概要
- TQBF問題のページへのリンク