Completude sob reduções injetivas de Karp

A redução de Karp é uma redução computável de muitos-um no tempo polinomial entre dois problemas computacionais. Muitas reduções de Karp são na verdade funções individuais. Isso levanta a questão de saber se toda redução de Karp é injetiva (função one-one).

Existe um natural de completo que é conhecido por completo apenas sob redução de um-Karp e não é conhecido por ser completo sob redução injetiva de Karp? O que ganhamos (e perdemos) se definirmos a completude de usando a redução injetiva de Karp? N $NP$$NP$

Um ganho óbvio é que conjuntos esparsos não podem ser completos com reduções injetivas de Karp.

Aqui está uma resposta para um caso especial, quando nos restringimos ao caso em que a redução de Karp também pode ser aumentada em comprimento , além de injetável. (Aumentar comprimento significa que , onde é a função que representa a redução.)$|f(x)|>|x|$$f$

Reivindicação: Se toda redução de Karp no puder ser transformada em um injetor e que aumenta o comprimento, o mantém.P ≠ N $NP$$P\neq NP$

Prova. Vamos supor que toda redução de Karp no possa ser transformada em uma que é injetável e aumenta o comprimento. Depois, existem duas possibilidades:$NP$

1. Todas essas reduções não são apenas computáveis ​​no tempo polinomial, mas o inverso de cada função, que existe após a injeção da função, também é computável no tempo polinomial. Sabe-se que se dois idiomas são redutíveis entre si por reduções computáveis ​​em politimo, invertível e polimotim, elas são isomórficas em politimo (ver Teorema 7.4 no livro "Teoria da complexidade computacional" de Ding-Zhu Du e Ker-I Ko). Isso significaria que todas as linguagens completas de são isomórficas , ou seja, a Conjectura de Isomorfismo mantém, o que é conhecido por implicar .p P ≠ N $NP$$p$$P\neq NP$

2. Há pelo menos uma entre essas funções, para as quais o inverso não é computável no tempo polinomial. Essa função forneceria um exemplo de uma função unidirecional de pior caso. Sabe-se, no entanto, que a existência de funções unidirecionais de pior caso também implica . (Veja o Teorema 2.5 no livro "The Complexity Theory Companion" de Hemaspaandra e Ogihara.)$P\neq NP$

Portanto, a suposição de que toda redução de Karp pode ser injetada e aumentar o comprimento implica , portanto é muito difícil provar isso. Por outro lado, pode ser mais fácil refutar, porque isso não parece ter uma consequência tão dramática. Também não está claro o que acontece se abandonarmos a suposição de aumento de comprimento.$P\neq NP$

Não, esse problema natural não é conhecido. A razão é que, tanto quanto eu sei, todos naturais problemas -Complete são conhecidos por serem p-isomorfo a SAT$\mathsf{NP}$ , eo Teorema Cook-Levin em mostras fato de que SAT é completo para sob reduções individuais. A combinação da redução de um para um SAT com um p-isomorfismo fornece uma redução de um para qualquer problema de p-isomórfico.$\mathsf{NP}$

De fato, mesmo os possíveis contra-exemplos "antinaturais" da Conjectura de Isomorfismo - os conjuntos k-criativos do Teorema 2.2 de Joseph e Young - estão completos sob reduções individuais por construção.

[Repetido do meu comentário aqui :] Como a maioria das reduções que criamos são de fato uma redução, por que não as estudamos quando elas são formalmente mais fortes e as obtemos na maioria das vezes? Eu acho que porque é mais simples não ter que provar a injetividade, mesmo que normalmente a tenhamos. Nesse sentido, talvez muitas reduções de um sejam as "reduções de Goldilocks": a potência certa, a simplicidade certa de prova.

Na verdade, reduções injetáveis ​​são úteis em criptografia. Suponha que você tenha um sistema de prova ZK para uma relação NP R sobre o idioma L. Se você deseja criar uma prova ZK para outra relação NP R 'sobre um idioma L', deve encontrar duas funções f e g com as seguintes propriedades : 1. x pertence a L 'se f (x) pertence a L, 2. Se (x, w) pertence a R' então (f (x), g (x, w)) pertence a R. 3. Além disso, , f e g devem ser eficientemente computáveis.

As propriedades acima implicam que, se o sistema de prova para R estiver completo e correto, o sistema de prova para R '(definido da maneira óbvia, usando as funções acima para reduzir instâncias de uma relação com a outra) estará completo e também com integridade.

Que tal provar que o novo sistema também é ZK ou indistinguível de testemunha (WI)? Se f for invertível, você pode provar que o sistema de prova obtido é ZK. Caso contrário, para provar que você deve assumir que o sistema de prova para R é ZK de entrada auxiliar (em vez de apenas ZK). Para WI, se f for invertível, você pode provar que o sistema de prova para R 'é WI. Sem o fato de que f é invertível, não tenho certeza se você pode provar que