充足可能性問題（以下，ＳＡＴ問題と略す）とは，
理論計算機科学で最も基本的で
重要な ＮＰ完全問題 の一つである．
グラフ理論における
巡回セールスマン問題，頂点彩色問題，独立頂点集合問題，
オペレーションズ・リサーチにおける整数計画問題，
ゲーム・パズルにおける数独，テトリスなど，
実社会で遭遇する多くの（決定）問題がＮＰ完全問題である．
その中でも，
ＳＡＴ問題は，そのＮＰ完全性が示された最初の問題である．
以下の意味で，
ＳＡＴ問題は，ＮＰ完全問題の根本である：
すべてのＮＰ完全問題のＮＰ完全性は， （いくつかの例外を除いて） ＳＡＴ問題からの有限回の多項式時間還元を経て示された．例えば， 教科書 [1] では， ハミルトン閉路問題は， 頂点被覆問題からの多項式時間還元により， 更に， 頂点被覆問題はＳＡＴ問題からの多項式時間還元によりＮＰ完全性が示されている． 更に， ハミルトン閉路問題からの 多項式時間還元が示されるＮＰ完全問題も数多く存在する． （もちろん，ＳＡＴ問題からの直接の還元， 更には，ＳＡＴ問題のＮＰ完全性が示されたように， 任意のＮＰ問題からの多項式時間還元を示すことができるはずだが， 証明がより複雑になることでしょう．）
ＳＡＴ問題は，以下のような問題である：
ψ = x1 (x1v x2) (x1vx2v x3) (x2vx3v x4) (x3vx4v x5) (x1vx2v x3vx4vx5)が入力として与えられたとする． ここで， x は x の 否定を表す． また，ψ を構成する一つ一つの (xv . . . ) を節と呼ぶ． この場合，上の ψ は充足可能である． なぜなら， 変数 x1, x2, x3, x4, x5 への割り当てを， (x1, x2, x3, x4, x5) = (1,1,1,1,1) とした場合， ψ のそれぞれの節は 1 となり， それゆえ ψ が 1 となるからである． 一方，
ψ = x1 (x1v x2) (x1vx2v x3) (x2vx3v x4) (x3vx4v x5) (x1vx2v x3vx4vx5)の場合， この ψ は充足不可能である．（なぜ？）
では，このような根本的な問題をどうやって （どのようなアルゴリズムで）解いたらよいでしょうか？ ＳＡＴ問題はＮＰ完全問題であるから， 多項式時間で解くことはかなり難しいことでしょう． 現実的ではないが， 指数時間かけてもよいとすると， 以下のような全探索アルゴリズムがＳＡＴ問題を解くこと分かる： ψ を n 変数上の CNF 論理式とした場合，
bruteforce(ψ)このアルゴリズムの（最悪）計算時間は O(|ψ|• 2n) となる． （以降では， 指数時間における多項式要素は省略して表記する． 例えば， O(|ψ|• 2n) は O(2n) と表記される．） では， ＳＡＴ問題を， 例えば， O(1.999n) 時間で解くことはできなでいだろうか？ 残念ながら， 今（２０１１年７月）のところ，そのようなアルゴリズムは見つかっていない．
{
for each t ∈ {0,1}n
if (ψ が割り当て t により充足する), then output YES
output NO
}
そのような一般のＳＡＴ問題ではなく， 以下のようなＳＡＴ問題の特殊な問題， k-SAT 問題，ならばそれが可能である：
ψ = x1 (x1v x2) (x1vx2v x3) (x2vx3v x4) (x3vx4v x5) (x3vx4vx5)ここで， 以下の基本的な事実を確認しておく：
任意の整数 k ≥ 3 に対して，k-SAT 問題はＮＰ完全である． 一方，2-SAT 問題は多項式時間で解くことができる．ＳＡＴ問題と同様， k ≥ 3 であれば， k-SAT 問題を多項式時間で解くことはかなり難しいことでしょう． しかし， k が定数であれば， 少し工夫することにより， k-SAT 問題を O((2-ε)n) 時間で 解くことができる（ε は k に依存した正の定数）：
simple-ksat(ψ)ここで，ψ|a とは， ψ に割り当て a を適用して得られる論理式のことである． 簡単な漸化式を解くことにより， このアルゴリズムの計算時間が O((2k-1) n/k) となることが分かる． （k = 3 の場合は，O(1.913n) となる．）
{
if (ψ が充足している), then output YES
if (ψ が充足していない), then return
ψ の任意の節 C を選ぶ
for each a ∈ {0,1}k
if (C が a で充足する), then simple-ksat(ψ|a)
}
上のアルゴリズムを少し改良することにより， より高速のアルゴリズムが得られる：
simple-ksat2(ψ)ここで， 例えば，任意に選んだ節 C が C= (x1vx2vx3) の場合， a = 1, 10, 100 による３つの 再帰呼び出し simple-ksat2(ψ|a) が実行される． 簡単な漸化式を解くことにより， このアルゴリズムの計算時間が O(cn) となる ことが分かる． ただし，c は次の方程式を満たす唯一の正の実数解である： tk -tk-1 - ... -t2-t-1=0 （k = 3 の場合は，O(1.841n) となる．）
{
if (ψ が充足している), then output YES
if (ψ が充足していない), then return
ψ の任意の節 C を選ぶ
// ここで，アルゴリズムの記述を簡略化させるため， C がすべて正のリテラルから成るとする
for i : 0 ≤ i ≤ |C|-1
a = 10i
simple-ksat2(ψ|a)
}
以上より， k-SAT 問題は， 明らかな計算時間 O(2n) よりも高速に解けることが分かった． では，k-SAT 問題はどのくらい高速に解くことができるのだろうか？ 現在（２０１１年７月）のところ， 最速の決定性アルゴリズムの計算時間は， O((2(k-1)/k)n) となって いる [2]． （この式に k = 3 を代入すると， 3-SAT 問題は O(1.3334n) で解けることとなる．） 特に， 3-SAT 問題に対してはさらなる高速化が図られ， 最速は O(1.3303n) となって いる [3]． （更に， 「乱択」アルゴリズムを使うことにより，さらなる高速化が図られている． 例えば， 3-SAT 問題を解く最速の乱択アルゴリズムの計算時間は， O(1.308n) となって いる [4]．）
理論計算機科学の分野に， 「P v.s. NP」という大きな未解決問題がある． 問題クラス P が NP に真に包含されているかどうかを問う問題である． （詳しくは ここ や ここ を参照．） 現在（２０１１年７月）， 多くの研究者が P≠NP と予想している． つまり， ＳＡＴ問題や k-SAT 問題が多項式時間では解けないと予想されている． アルゴリズムというのは， 通常，とりわけ実社会での応用を考えた場合は， 多項式時間計算可能な問題に対してその存在意義が認められる． では，なぜ， 多項式時間では解けそうにもない ＳＡＴ問題を解く（指数時間）アルゴリズムを研究するのでしょうか？
先の P≠NP というのはあくまで予想であって証明された事実ではないが， 仮に，真実が P≠NP であったとする． ここで，将来， 3-SAT 問題を解く O(1.2999n) 時間（決定性）アルゴリズムが 開発されたとする．（このアルゴリズムを A とする．） 更に，将来， コンピュータの性能が向上して， 指数時間かかるアルゴリズムも， ある程度の大きな長さの入力を扱えるようになったとする． 例えば， n = 1000 に対して， O(1.2999n) 時間アルゴリズム A の実行が （最新のスーパーコンピュータを使って）１日以内で終了したとする． 一方で，仮に， 現在（２０１１年７月）の 3-SAT 問題を解く最速のアルゴリズム， O(1.3303n) 時間（決定性）アルゴリズム， の開発以降この研究が停滞して， これが最速のままであったとする． （このアルゴリズムを B とする．） この場合， 1.3303/1.2999 ≈ 1.0234 より， アルゴリズム B の実行には， （最新のスーパーコンピュータを使っても） 1.02341000 ≈ 1.110310 日， およそ三千年もの年月を要することになる． （異なる二つの指数関数の比もまた指数関数となる！） コンピュータの性能が向上すればするほど扱える n の範囲が大きくなり， それゆえ， 二つのアルゴリズムの計算時間（を表す指数の底）が１００分の１でも異なれば， その比，すなわち二つのアルゴリズムの優劣が顕著に表れる． これが， 指数時間アルゴリズムの研究が滞ってはならない大きな理由である．
蛇足： 先の未解決問題「P v.s. NP」についておもしろい調査がある． ２００２年，William Gasarch が理論計算機科学者を対象に， ある投票を行った [5]． （２０１１年７月にも，彼は新たな投票を募るとして，第２回目の調査を始めた．） その（２００２年の）投票結果で注目すべきことは， 予想の明言を控えた研究者が少なくなかったことである． （単純に，その調査自体に興味がなかっただけかもしれないが．） 更に， Bela Bollobas（ランダムグラフ） や Paul Vitanyi（コルモゴロフ計算量）といったその分野の権威が， 大胆にも P=NP と予想したことも興味深い． （どの程度本気なのかは分からないが．） このことから言えることは， P=NP であるという可能性が限りなくゼロに近いということでもないことである． k-SAT 問題を解く指数時間アルゴリズムの高速化の延長に， 劣指数時間アルゴリズム，そして多項式時間アルゴリズムと， 大方の予想に反する P=NP という可能性を追求することは， それほど大それたことでもないのかもしれない．