Interseção de idiomas em NP

A interseção de dois idiomas no NP que não são NP completos pode ser NP completa?

A interseção de dois idiomas no coNP que não são completos no coNP pode ser completa no coNP?

A interseção de dois idiomas, um em coNP, mas não completo e outro em NP, mas não NP completo, pode ser NP completo ou coNP completo?

complexity-classes np T ....
fonte

Muito interessante. :)

Michael Wehar

Se P = NP, a resposta é NÃO. Nesse caso, os únicos idiomas que não estão completos em NP (completo em coNP) são o conjunto vazio e

Σ^{*}

$\Sigma^*$

quer

Se P não for igual a NP, existem problemas intermediários entre os ladders e NP ... qualquer exemplo que você sugeriria como natural. 1.

ARi

Respostas:

Apenas um comentário estendido para explicar melhor o comentário de ARi (eu estava escrevendo enquanto o via).

É suficiente usar uma abordagem de "grande espaço" semelhante à usada no teorema de Lardner; por exemplo:

$A_1 = \{ x \mid x \in SAT \land f(|x|) \text { is even}\} \cup \{x \mid f(|x|) \text{ is odd} \}$

$A_2 = \{ x \mid x \in SAT \land f(|x|) \text { is odd}\} \cup \{x \mid f(|x|) \text{ is even} \}$

$f$

$A_1, A_2$ $A_1 \cap A_2 = SAT$

Marzio De Biasi
fonte

A_{1}

$A_1$

A_{2}

$A_2$

{x ∣ x \in S A T \land f (| x |) is even}

$\{ x \mid x \in SAT \land f(|x|) \text{ is even}\}$

A_{1}

$A_1$

P \neq N P

$P \neq NP$

P = N P

$P = NP$

Não pode ser apenas sobre qualquer função polytime?

ARi

@ARi: não, ele deve ser lento o suficiente para criar grandes lacunas para impedir a completude do NP (para permitir a diagonalização atrasada). Vou tentar escrever uma prova formal nos próximos dias.

Marzio De Biasi

f

$f$