complexity-theory - 多項式時間近似スキームの理解

Question

近似アルゴリズムは多項式時間近似アルゴリズム (PTAS) と同じですか? たとえば、頂点カバーの A(I) <= 2 * OPT(I) を示すことができます。Vertex Cover には 2多項式時間近似アルゴリズムまたは PTAS があるということですか?

ありがとう！

注: 斜体のテキストは、質問を投稿した後に行った編集です。

Answer 1

いいえ、必ずしもそうとは限りません。PTAS は、任意の ε > 0 が与えられた場合に、答えを多項式時間で (1 + ε) の因数に近似できるアルゴリズムです。つまり、任意の適切な近似値を得ることができます。

特定の要因 (5/8 など) の近似アルゴリズムを持ついくつかの問題 (MAX-3SAT など) が知られていますが、P = NP でない限り、問題をどれだけ適切に近似できるかについて厳しい制限があることが知られています。多項式時間で。たとえば、PCP の定理は、P = NP でない限り、MAX-3SAT は多項式時間の 7/8 近似を持たないことを示しています。したがって、MAX-3SAT に PTAS がある可能性はありますが、それは P = NP の場合のみです。

お役に立てれば！