まず、これは私の宿題だと言いたい。ただし、私の問題を解決するために、必要な文献を使用できます。
問題はその名前から明らかだと思いますが、次のように説明します。サイズK.」
からおよび から3-SATへの多項式簡約について知っています。( http://mlnotes.com/2013/04/29/npc.html ) ただし、これら 2 つの削減を組み合わせることができないため、これには問題があります。からへの削減も試みましたが、あまり成功しませんでした。CLIQUE3-SATINDEPENDENT-SETCLIQUECLIQUE-OR-INDEPENDENT-SET
だから私は本当にヒントをいただければ幸いです！
前もって感謝します。