各行を異なるようにする列の最小数

私はこの問題がNP困難かどうか不思議です:あなたが任意の$ m times n $
0-1行列を与えられたとしましょう(各要素は問題の単純化のために0または1です) (つまり、0-1次元の次元 – $ n
$のベクトル)は異なります(つまり、反復行はありません)。私はこれらの列内の各行が異なるように最小限の列数を選択したいと思います。

正しく理解するためには、選択する列数の確かな下限$ log_2m $がありますが、サイズ$ log_2m
$の解が存在するかどうかはわかりません。さらに、各行が異なるので、サイズ$ n $の実現可能な解が存在しなければならない。

これを解決するための効率的なアルゴリズムはありますか?あるいは、私は$ log_2m $から$ n
$までの列の可能な組み合わせをすべて調べることで、brute-forthの方法でそれを解決する必要がありますか?

ベストアンサー

あなたの問題はNP困難であることが知られています。たとえばを参照してください

Vincent Froese、Renévan Bevern、Rolf Niedermeier、Manuel Sorge:
  「ベクトルを識別する次元を選択する際に隠れた構造を利用する」
  Journal of Computer and System Sciences
82、pp521-535(2016)。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です