Является ли задача «Меньше всего отличающихся битов» NP-полной?

Это имя, которое я сделал для этой проблемы. Я не видел нигде описанного ранее. Я пока не смог найти ни доказательства NP-полноты, ни алгоритма полиномиального времени для этой задачи. Это не проблема домашней работы - это связано с проблемой, с которой я столкнулся в своей работе.

НАИБОЛЕЕ ДИСКРИМИНАЦИОННЫЕ БИТЫ

INSTANCE: набор T, содержащий битовые векторы, где каждый битовый вектор имеет длину ровно N бит. Каждый элемент T уникален, как и следовало ожидать от набора в математике. Целое число K <N.

ВОПРОС: Существует ли набор B не более чем из K битовых позиций (т. Е. Целых чисел в диапазоне [0, N-1]), так что когда мы удаляем все биты, кроме тех, что в B, из каждого вектора в T, оставшиеся более короткие векторы все все еще уникален?

Пример 1. Для экземпляра N = 5, T = {00010, 11010, 01101, 00011}, K = 2, ответ - да, потому что мы можем выбрать битовые позиции B = {0,3}. Используя соглашение, что битовая позиция 0 является самой правой, а номера битовых позиций увеличиваются справа налево, удаляя все битовые позиции, кроме позиций в B, из векторов в T оставляет T '= {00, 10, 11, 01}, и все это уникально.

Пример 2: N = 5, T = {00000, 00001, 00010, 00100}, K = 2. Ответ - нет, потому что независимо от того, какие две битовые позиции мы выберем, ни один из 2-битных векторов не будет равен 11, поэтому по крайней мере два из 2-битных векторов будут равны друг другу.

Конечно, мы можем решить эту проблему, перечислив все (N выбирают K) подмножеств с размером K из N позиций битов и определив, какие из них удовлетворяют условию вопроса. Тем не менее, это экспоненциально в размере ввода.

Эта проблема является NP-полной. Доказательство, основанное на сокращении с 3-SAT, выглядит следующим образом:

Рассмотрим пример 3-SAT с переменными и m предложениями. Построим 2 n + 2 m битовых вектора («строки») длиной 2 n + ⌈ log 2 ( n + m ) such , так что наименьшее количество различающих битов будет n + ⌈ log 2 ( n + m ) ⌉ если исходный экземпляр 3-SAT является удовлетворительным.$n$$m$$2n + 2m$$2n + \lceil \log_2(n + m) \rceil$$n + \lceil \log_2(n + m) \rceil$

Первые биты будут соответствовать литералам { х 1 , ¬ х 1 , х 2 , ¬ х 2 , . , , , x n , ¬ x n } . Что касается этих битов, первые 2 м строк будут приходить парами, первая из которых будет иметь 1 для каждого литерала, включенного в соответствующее предложение, а вторая из которых будет полностью состоять из 0 . Оставшиеся 2 $2n$$\left\{ x_1, \neg x_1, x_2, \neg x_2, ..., x_n, \neg x_n \right\}$$2m$$1$$0$$2n$строки также будут приходить парами, первая из которых будет иметь для соответствующего литерала и его отрицания, а вторая будет полностью состоять из 0 . Наконец, последние ⌈ log 2 ( n + m ) ⌉ будут использоваться для «подписания» каждой пары строк с ее индексом от 0 до n + m - 1 , записанным в двоичном виде.$1$$0$$\lceil \log_2(n + m) \rceil$$0$$n+m-1$

Чтобы отличить каждую «буквальную» строку от ее преемника, необходимо сохранить либо бит, соответствующий этому литералу, либо бит, соответствующий его отрицанию. Кроме того , для того , чтобы различить среди «нулевой» + индекс строки, все ⌈ войти 2 ( п + т ) ⌉ индексные биты должны быть сохранены. Поэтому минимально возможное количество различающих битов равно n + ⌈ log 2 ( n + m ) $n+m$$\lceil \log_2(n + m) \rceil$$n + \lceil \log_2(n + m) \rceil$, Наконец, чтобы отличить каждую строку «предложения» от ее преемника, должен быть сохранен, по крайней мере, один из трех битов, соответствующих литералам, включенным в это предложение. Если экземпляр 3-SAT выполним, это последнее условие не потребует каких-либо дополнительных битов (в частности, нам не нужно сохранять биты, соответствующие как и ¬ x i для любого i ); и наоборот, если есть n + ⌈ log 2 ( n + m ) ⌉ битов, которые различают все 2 n + 2 m битовых векторов, они должны содержать ровно один из$x_i$$\neg x_i$$i$$n + \lceil \log_2(n + m) \rceil$$2n+2m$ и ¬ x i для каждого i и, следовательно, соответствуют удовлетворительному назначению значений истинности для n переменных.$x_i$$\neg x_i$$i$$n$

Хотя доказательство NP-полноты уже предоставлено, возможно, стоит отметить, что эта проблема эквивалентна известной проблеме NP-завершенности, называемой проблемой минимального набора тестов ([SP6] у Гэри и Джонсона , также называемой минимальным набором тестов). проблема ): просто поменяйте роль наборов и роль позиций.