TQBF問題

ウィキペディア

TQBF問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/08/29 04:56 UTC 版)

計算複雑性理論において、言語TQBFは量化された真のブール式からなる形式言語である。(完全に)量化されたブール式とは、すべての変数が存在量化子や全称量化子を用いて式の先頭で量化(束縛)された限定命題論理の式である。自由変数が存在しないため、そのような式は真あるいは偽と同値である。もし真と同値ならば、その式は言語TQBFの要素である。この言語はQSAT(量化されたSAT, Quantified SAT)としても知られている。

概要

計算複雑性理論において、量化されたブール式問題(QBF)は充足可能性問題の一般化であり、変数を存在量化子でも全称量化子でも量化することができる。言い換えると、QBFはブール変数の集合の上の量化された式が真か偽かを問うものである。例えば、以下の式はQBFのインスタンスである:

$\forall x\ \exists y\ \exists z\ ((x\lor z)\land y)$ この項目は、応用数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。