配列のすべてのサブセットの最大OR値

Question

n個の整数の配列が与えられます。指定された配列のすべてのサブセットの中で最大のOR値を持つサブセットの最小長さを求めます。

これを解決するにはどうすればいいですか？

Answer 1

最大ORはすべての項目のORです。実際の問題は、その値とORする最小のサブセットを見つけることだけです。

これはSet Coverの問題の検索バージョンです。Set Coverの検索バージョンのインスタンスとして扱うことで明らかに解決できるという意味で、Set Coverインスタンスを書くことができるという意味でこの問題の面ではNP困難（決定問題ではないためNP完備ではない）です。

整数線形計画法、SAT解法（SATは最適化されないために複数のクエリが必要です）、動的計画法、疑いなく他の手法を使っても解決できます。