A NP-completude / dureza precisa ser construtiva?

11

Existe algum com as seguintes propriedades: $L\in {\bf NP}$

É sabido que implica . $L\in {\bf P}$ ${\bf P}={\bf NP}$
Não há (conhecido) tempo polinomial redução Turing de (ou algum outro problema -completo) para . $SAT$ ${\bf NP}$ $L$

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? $L$ ${\bf NP}$ ${\bf P}$ $L$ ${\bf NP}$ $constructive$ $SAT$ $L$

cc.complexity-theory np-hardness reductions 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

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. $\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{P}\neq\mathsf{NP}$

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. $L$ $\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{P}\neq\mathsf{NP}$ $L$ $\mathsf{NP}$ $\mathsf{NP}=\mathsf{P}$

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

A resposta depende do que queremos dizer com "construtivo". Classicamente, um problema de decisão é definido como -hard iff $A$ $\mathsf{NP}$

\forall B \in N P B \leq_{m}^{P} A

$\forall B\in \mathsf{NP} \ B \leq^\mathsf{P}_m A$

que significa

\forall B \in N P \exists f \in F P \forall x \in {0, 1}^{*} (x \in B \leftrightarrow f (x) \in A)

$\forall B\in \mathsf{NP} \ \exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in B \leftrightarrow f(x)\in A)$

E pelo teorema de Cook isso é equivalente a

S A T \leq_{m}^{P} A

$SAT \leq^\mathsf{P}_m A$

que significa

\exists f \in F P \forall x \in {0, 1}^{*} (x \in S A T \leftrightarrow f (x) \in A)

$\exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in SAT \leftrightarrow f(x)\in 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. $A$ $f$

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.

N P

$\mathsf{NP}$

P

$\mathsf{P}$

P \neq N P

$\mathsf{P}\neq\mathsf{NP}$

N P

$\mathsf{NP}$

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

$k$

k

$k$

f (k)

$f(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

A NP-completude / dureza precisa ser construtiva?

Respostas: