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.
[続きの解説]
「TQBF問題」の続きの解説一覧
- 1 TQBF問題とは
- 2 TQBF問題の概要
このページでは「ウィキペディア」からTQBF問題を検索した結果を表示しています。
Weblioに収録されているすべての辞書からTQBF問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からTQBF問題を検索
Weblioに収録されているすべての辞書からTQBF問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からTQBF問題を検索 - TQBF問題のページへのリンク
