Interseção de idiomas em NP

8

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?

T ....
fonte
Muito interessante. :)
Michael Wehar
2
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 . Σ
quer
3
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:

19

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:

A1={xxSATf(|x|) is even}{xf(|x|) is odd}

A2={xxSATf(|x|) is odd}{xf(|x|) is even}

f

A1,A2A1A2=SAT

Marzio De Biasi
fonte
2
A1A2
{xxSATf(|x|) is even}A1PNPP=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