O problema "Menos bits discriminantes" está NP-completo?

Esse é um nome que eu inventei para esse problema. Eu nunca vi isso descrito em nenhum lugar antes. Ainda não consegui encontrar uma prova de completude de NP nem um algoritmo de tempo polinomial para esse problema. Não é um problema de lição de casa - está relacionado a um problema que encontrei no meu trabalho.

POBRES MAIS DISCRIMINANTES

INSTANCE: Um conjunto T contendo vetores de bits, onde cada vetor de bit tem exatamente N bits de comprimento. Cada elemento de T é único, como seria de esperar de um conjunto de matemática. Um número inteiro K <N.

PERGUNTA: Existe um conjunto B na maioria das posições de K bits (ou seja, números inteiros no intervalo [0, N-1]), de modo que, quando removemos todos os bits, exceto aqueles em B, de cada vetor em T, os demais vetores menores são todos ainda é único?

Exemplo 1: Para a instância N = 5, T = {00010, 11010, 01101, 00011}, K = 2, a resposta é sim, porque podemos selecionar as posições de bits B = {0,3}. Usando a convenção de que a posição do bit 0 é a mais à direita e os números da posição do bit aumentam da direita para a esquerda, removendo todas as posições de bits, exceto aquelas em B dos vetores em T, deixa T '= {00, 10, 11, 01}, e esses são todos únicos.

Exemplo 2: N = 5, T = {00000, 00001, 00010, 00100}, K = 2. A resposta é não, porque, independentemente de quais posições de dois bits selecionamos, nenhum dos vetores de 2 bits será igual a 11; portanto, pelo menos dois dos vetores de 2 bits serão iguais um ao outro.

Naturalmente, podemos resolver esse problema enumerando todos os subconjuntos (N, escolha K) com o tamanho K das posições de bits N e determinando quais satisfazem a condição da pergunta. No entanto, isso é exponencial no tamanho da entrada.

Este problema está NP-completo. Uma prova baseada na redução do 3-SAT é a seguinte:

Considere uma instância de 3-SAT com variáveis ​​e cláusulas m . Construiremos 2 vetores de bits n + 2 m ("linhas") de comprimento 2 n + ⌈ log $n$$m$$2n + 2m$ , de modo que o menor número de bits discriminantes seja n + ⌈ log 2 ( n + m ) ⌉ se a instância 3-SAT original for satisfatória.$2n + \lceil \log_2(n + m) \rceil$$n + \lceil \log_2(n + m) \rceil$

Os primeiros bits de corresponderão aos literais { x 1 , ¬ x 1 , x 2 , ¬ x 2 , . . . , X n , ¬ x n } . Com relação a esses bits, as duas primeiras linhas de 2 m virão em pares, a primeira das quais terá 1 para cada literal incluído na cláusula correspondente e a segunda das quais consistirá inteiramente de 0 's. Os restantes 2 $2n$$\left\{ x_1, \neg x_1, x_2, \neg x_2, ..., x_n, \neg x_n \right\}$$2m$$1$$0$$2n$linhas também virão em pares, o primeiro dos quais terá 's para o literal correspondente e sua negação, e o segundo dos quais consistirá inteiramente de 0 ' s. Finalmente, os últimos ⌈ log 2 ( n + m ) ⌉ bits serão usados ​​para "assinar" cada par de linhas com seu índice, de 0 a n + m - 1 , escrito em binário.$1$$0$$\lceil \log_2(n + m) \rceil$$0$$n+m-1$

Para distinguir cada linha "literal" de seu sucessor, o bit correspondente a esse literal ou o bit correspondente à sua negação deve ser retido. Além disso, para discriminar entre as linhas "zero + índice", todos os bits de índice ⌈ log 2 ( n + m ) must devem ser retidos. O número mínimo possível de bits discriminantes é, portanto, n + ⌈ log 2 ( n + m ) $n+m$$\lceil \log_2(n + m) \rceil$$n + \lceil \log_2(n + m) \rceil$. Finalmente, para distinguir cada linha da "cláusula" de seu sucessor, pelo menos um dos três bits correspondentes aos literais incluídos nessa cláusula deve ser retido. Se a instância 3-SAT é satisfiable, esta última condição não vai exigir qualquer bits extras (em particular, não precisamos de reter os bits correspondentes a ambos e ¬ x i para qualquer i + ⌈ log 2 ( n + m ) ⌉ bits que discriminam entre todos os vetores de 2 n + 2 m bits, eles deverão conter exatamente um dos$x_i$$\neg x_i$$i$); e, inversamente, se houver $n + \lceil \log_2(n + m) \rceil$$2n+2m$ e ¬ x i para cada i , e, portanto, corresponde a uma atribuição de satisfazer de valores lógicos para os n variáveis.$x_i$$\neg x_i$$i$$n$

Embora já seja fornecida uma prova de completude do NP , vale a pena ressaltar que esse problema é equivalente a um problema completo do NP conhecido chamado problema mínimo do conjunto de testes ([SP6] em Garey e Johnson , também chamado de coleta mínima de testes problema ): apenas troque o papel dos sets e o papel das posições.