np - Strong NP 完全問題に FPTAS を使用できない理由

Question

FPTAS は 0-1 ナップザックのような弱い NP 問題に適用できることがわかりました。

しかし、ビン パッキングのような強力な NP 問題に同じ原則を適用できないのはなぜですか。同じことについて wiki ページもチェックしましたが、ほとんど理解していませんでした。

Answer 1

強力な NP 完全問題に FPTAS がある場合、近似アルゴリズムを「だまして」最適解を与えることができます。詳細はこちら: http://www.idi.ntnu.no/~mlh/algkon/complexity.pdf

この FPTAS の存在により、NP 完全問題の多項式時間アルゴリズムが得られます。