2011-12-18 7 views
1

PはComplexity TheoryのP-Completeと同じですか? 私は2つのクラスが同一かどうかを知る必要があります。私はいずれか2つの間でKarpの削減を持っているので、インターネット上でそれを見つけることはできません。PはP-Completeと同じですか?

答えて

2

P内の任意の問題が多項式時間短縮することができる(両方とも1対多および チューリング)「ほとんど」を言うための唯一の理由があるP.

ほとんど、他の問題に他の問題が多数ある可能性がある1つの問題(および の補完)があるため、 に縮小されます(Turingは縮小されますが)。 すべてを受け入れる問題(すべてを拒否する問題)

出典:Wikipedia P-完全性、多項式時間還元よりも縮小の弱い形の話をするとき通常は、あなたがリストされている理由のために使用されている

+1

。通常、logspaceやAC^0還元性のようなものが使われます。 –

関連する問題