A NP-completude / dureza precisa ser construtiva?

11

Existe algum com as seguintes propriedades:LNP

  1. É sabido que implica .P = N PLPP=NP

  2. Não há (conhecido) tempo polinomial redução Turing de (ou algum outro problema -completo) para .N P LSATNPL

Em outras palavras, se um algoritmo polinomial de tempo para implica o colapso de em , é necessário que essa "dureza geral" de para seja de alguma forma , no sentido de que, digamos, o deve ser redutível a através de alguma redução específica?N P P G N P c o n s t r u c t i v e S A T GLNPPLNPconstructiveSATL

Andras Farago
fonte
10
Parece-me que o título e o corpo fazem duas perguntas diferentes. Por exemplo, a resposta de Kaveh funciona para a pergunta no corpo, mas não para a pergunta no título.
precisa

Respostas:

15

Sim, existem tais conjuntos, use qualquer conjunto intermediário (qualquer conjunto que seja provável assumindo ), por exemplo, construa um do SAT usando o teorema de Ladner.N P PN PNPNPPNP

Observe que seu precisa considerar um problema intermediário , pois está em mas não está completo para isso. Observe também que você está assumindo que caso contrário, não haverá pois todos os problemas não triviais estariam completos para se . Além disso, as condições que você forneceu não implicam integridade, portanto a pergunta na primeira parte não é a mesma que a questão sobre a construtividade da integridade.N P N P PN P L N P N P = PLNPNPPNPLNPNP=P


Em relação à pergunta no título, ou seja, "a dureza precisa ser construtiva?".NP

A resposta depende do que queremos dizer com "construtivo". Classicamente, um problema de decisão é definido como -hard iffN PANP

BNP BmPA

que significa

BNP fFP x{0,1} (xBf(x)A)

E pelo teorema de Cook isso é equivalente a

SATmPA

que significa

fFP x{0,1} (xSATf(x)A)

Como podemos tornar essa definição construtiva? Já me parece muito construtivo. Acho que o que você quer perguntar é se podemos provar isso para alguns sem saber o que é explicitamente. Não me lembro de ter visto essa prova de dureza.fAf

Classicamente, mesmo quando não temos uma função específica, existe uma função, dizendo que é impossível que nenhuma função seja uma redução seja equivalente a dizer que alguma função é uma redução. Para falar sobre construtividade, precisamos ser mais atenciosos. Por exemplo, podemos falar sobre afirmações que são prováveis ​​classicamente, mas não construtivamente (por exemplo, intuicionismo onde diferentes estados do conhecimento matemático fazem sentido, procure no Google por "matemático ideal" ou verifique isso ).

Intuitivamente, parece-me plausível que possamos provar tal afirmação usando uma prova por contradição e sem atribuir nenhuma função explícita de redução. Mas isso não significa que não há prova construtiva da declaração. Para dizer mais que não existe prova construtiva, precisamos ser mais específicos: provas em que teoria / sistema? o que queremos dizer com prova construtiva?

Kaveh
fonte
Por quê? Um algoritmo de tempo P para um problema intermediário implica P = NP?
Mohammad Al-Turkistany
1
@ Mohammed, a definição de um problema intermediário afirma que ele não está em e sabemos que implica que o problema é intermediário. P PN P N PNPPPNPNP
Kaveh
12

Você pode estar interessado nos conjuntos criativos, inventados em [1] como um contra-exemplo conjecturado da conjectura de Berman-Hartmanis, de que todos os conjuntos completos NP são isomórficos ao SAT.k

"Isomorphic" é diferente de uma redução de Turing (de fato significativamente mais fraca), mas esses conjuntos mostraram ser NP-hard diretamente e, tanto quanto eu sei, não há redução conhecida no SAT. Dito isso, pela definição de NP-completude deve haver alguma redução entre os dois, portanto, embora isso atenda ao critério de redução "não conhecida", pode não ser exatamente o que você está procurando.

[1] Joseph, D. e Young, P. Algumas observações sobre funções de testemunha para conjuntos não polinomiais e não completos em PN. Ciência da Computação Teórica. vol. 39, p. 225--237. 1985. Elsevier.

SamM
fonte
6

A seguir, é apresentado um exemplo para a pergunta no título. Retirado do seguinte artigo: Jan Kratochvil, Petr Savicky e Zsolt Tuza. Mais uma ocorrência de variáveis ​​faz com que a satisfação salte de trivial para np-complete. SIAM Journal on Computing, 22 (1): 203-210, 1993.

Seja f (k) o número inteiro máximo r de modo que todos os fóruns do k-SAT nos quais cada variável ocorre na maioria dos r vezes sejam satisfatórios. Não se sabe se f (k) é computável, embora limites relativamente estreitos sejam conhecidos por ela (ver H. Gebauer, R. Moser, D. Scheder e E. Welzl. O lema local e a satisfação de Lov ́asz. páginas 30–54, 2009.).

(k, s) -SAT é o problema k-SAT restrito ao fórum em que cada variável ocorre na maioria das vezes.

Kratochvil et al. provou que (k, f (k) +1) -SAT é NP-completo. Observe que os problemas (k, f (k)) - SAT são sempre satisfatórios (por definição). A redução em si não é construtiva: observe que a redução gera uma fórmula na qual cada variável ocorre no máximo f (k) +1 vezes, mesmo que f (k) não seja conhecido por ser computável. A principal idéia não construtiva é que, embora o valor f (k) seja desconhecido, existe uma fórmula (k, f (k) +1) -SAT que não é satisfatória e eles manipulam essa fórmula de acordo com suas necessidades .

Ou Sattath
fonte
2
+1. IIUC, o que está dizendo é que uma classe de problemas dependendo de é NP-completa, mas não se sabe que as reduções sejam computáveis ​​uniformemente a partir de . (Mas também os próprios problemas não são uniformemente computably enumeráveis uma vez que não sei como calcular por isso não é de estranhar que as reduções não são uniformemente computável.)k f ( k )kkf(k)
Kaveh
1
@ Kaveh De fato, a redução não é computável, mas o problema em si é: (k, s) -SAT está claramente em NP para cada s. O parâmetro que torna o problema NP-completo, ou seja, f (k) +1, é o objeto que não é computável.
Ou Sattath
2

Agrawal e Biswas apresentaram uma linguagem NP-completa para a qual não há redução conhecida de Karp ou Cook. A prova de completude segue porque sua relação de testemunha é universal (a relação de testemunha tem os operadores de junção e equivalência necessários para ser universal). O idioma é dado na seção 6.3 na referência.

M.Agrawal, S.Biswas, Relações universais em procedimentos IEEE Conferenceon Structure in Complexity Theory (1992), pp. 207-220.

Mohammad Al-Turkistany
fonte
1
Uma linguagem NP-completa é, por definição, completa em reduções de Karp, então o que significa a primeira frase?
Emil Jeřábek 3.0 28/08
@ EmilJeřábek Significa exatamente o que diz, não há redução conhecida de Karp ou Cook. Agrawal e Biswas provaram que Conjuntos com relações universais são NP-completos. Eu sugiro que você leia o jornal.
Mohammad Al-Turkistany
1
Não, não pode significar o que diz, porque o que diz não faz sentido. Algo que não se sabe estar completo com as reduções de Karp é, a fortiori, que se sabe que não está completo. Percorri o resumo e a introdução do artigo e ainda não encontrei nada que correspondesse à sua descrição.
Emil Jeřábek 3.0 28/08
@ EmilJeřábek Leia atentamente a seção 6.3. Tenho medo de que desnatação não é suficiente neste caso :)
Mohammad Al-Turkistany
1
@ MohammadAl-Turkistany, acredito que o argumento é que as declarações "não são conhecidas por serem completas sob reduções de K." e "não há redução de K. conhecida" têm significados diferentes. O post diz uma coisa e seu comentário diz a outra.
usul