Um subconjunto de um problema NP-completo pode estar em P?

O problema é NP-completo (comprovado) para todos os dados de entrada (sem exceção).

Assumimos que P! = NP.

É possível que exista um subconjunto (infinitamente grande) do problema, para o qual esse subconjunto esteja em P?

Questão teórica.

Sua pergunta não faz sentido:

O problema é NP-completo (comprovado) para todos os dados de entrada (sem exceção).

Isso não é uma coisa. NP-completeness é uma propriedade de conjuntos inteiros, não de entradas específicas. É bastante trivial mostrar que, se você escolher uma entrada específica, qualquer problema será$O(1)$nessa entrada: você apenas envia sim ou não, dependendo do que for correto para sua entrada. Quando você faz isso, todas as análises de algoritmos são interrompidas e tudo acaba sendo inútil. Então, nós não fazemos isso.

$P$, $NP$, $NP$- complexidade , tempo polinomial etc. estão todos relacionados à complexidade assintótica : à medida que o tamanho da entrada aumenta, como o tempo de execução cresce? Isso só faz sentido quando você olha através de entradas diferentes, da mesma forma que a derivada de um ponto no cálculo é uma propriedade que leva em consideração a curva ao redor do ponto.

Assumimos que P! = NP.

Novamente, isso não afeta sua resposta. E se$P = NP$, então todo $P$ conjunto é $NP$-complete, ^* para que haja vários subconjuntos em$P$. E se$P=NP$, os exemplos que as pessoas deram são todos válidos.

É possível que exista um subconjunto do problema (infinitamente grande), que esse problema esteja em P?

Sim, e as outras respostas deram ótimos exemplos disso. Mas para a posteridade, aqui está outro exemplo de contra-exemplo.

• $k$-coloring is $NP$-complete se você tomar $k$ como entrada, mas $2$-coloring é um subconjunto infinito disso que está em $P$.

^{* Exceto por $\emptyset$ e $\Sigma^*$, que não são $NP$- completo por razões técnicas relacionadas à forma de reduções que usamos para definir a integridade.}

Na verdade, você não precisa do P$\,\neq\,$Hipótese NP , uma vez que existem infinitos subconjuntos decidíveis em tempo constante de problemas completos de NP . Para qualquer idioma completo do NP$L\subseteq\{0,1\}^*$, deixei $L' = \{0w\mid w\in L\}\cup\{1w\mid w\in\{0,1\}^*\}$. $L'$ ainda está completo com NP (redução trivial de $L$), mas contém o subconjunto infinito decidível em tempo constante de todas as cadeias que começam com $1$.

Pelo que entendi sua pergunta, sim, isso é possível. Como exemplo, considere o subconjunto (infinitamente grande) de SAT que contém todas as fórmulas satisfatórias sem negações. Esse subconjunto está trivialmente em P.

Veja o exemplo de $\mathsf{3\text{-}Coloring}$ problema, é $\mathsf{NP\text{-}Complete}$ em geral, mas para as árvores (são infinitas), está em $\mathsf{P\text{}}$

Coloração de gráfico, clique máximo e conjunto máximo independente são $\mathcal{NP}$-complete (versões de decisão), mas polinomial em gráficos perfeitos.

Considere o problema do Vendedor ambulante: Dadas são n cidades e as distâncias entre cada par de cidades e um limite d. Existe uma rota tocando cada cidade uma vez e depois retornando ao ponto de partida com um comprimento total ≤ d?

Para qualquer conjunto de cidades e distâncias, para valores pequenos de d ("pequeno", dependendo das distâncias), será fácil mostrar que não há solução e, para valores grandes de d, é fácil encontrar uma solução. Portanto, você pode encontrar um subconjunto do problema em que d é grande ou pequeno o suficiente para resolver qualquer instância em tempo polinomial.