チェンの「2-MAXSAT問題は多項式時間で解決可能」での批判

本論文では、楊軍チェンの技術報告書「2-MAXSAT問題は多項式時間で解決可能」Che23を検討します。この報告書は、同名の会議論文Che22を修正し、拡張したものです。チェンの論文は、2-CNF式をグラフに変換して探索することで、NP完全問題2-MAXSATの多項式時間アルゴリズムを構築することを目的としています。我々は、複数の反例を通じて、チェンの提案したアルゴリズムには欠陥があることを示し、彼らが作成した構造が適切に形式化された定義を欠いていることを発見しました。さらに、著者が自らのアルゴリズムの正当性を証明できていないこと、及び提案する解法の時間分析において過度な一般化を行っていることについて詳述します。これらの問題により、チェンの技術報告書Che23および会議論文Che22はどちらもP=NPの証明を提供できないと結論付けます。