Poderia ser fácil calcular o número cromático quando a coloração é difícil para alguma classe gráfica?

Pergunta semelhante foi feita antes, mas houve um erro, por isso foi deixada sem resposta Classe Graph com número cromático fácil, mas coloração NP-difícil

Existe algum conjunto infinito de gráficos , como:$C$

1. Existe um algoritmo polinomial que reconhece para cada gráfico se G pertence a C$G$$G$$C$

2. Existe um algoritmo de tempo polinomial que calcula o número cromático $\chi(g)$ para cada $g \in C$

3. A humanidade não conhece um algoritmo de tempo polinomial para calcular a coloração adequada para $C$ , ou (o que é melhor), há uma prova de que esse algoritmo (sob suposições razoáveis) não existe.

Sim. Como 3-COLORING é FNP-complete, para qualquer problema no FNP, podemos construir um gráfico G que é de 3 cores se e somente se o problema tiver uma solução. Portanto, você pode escolher o seu problema favorito em TFNP \ FP (se não estiver vazio!), Como encontrar um fator de um número composto ou um segundo ciclo hamiltoniano em um gráfico tridimensional e convertê-lo em um gráfico.

Mais detalhadamente com o exemplo de encontrar um fator. Vamos fixar um algoritmo que converte um número composto em um gráfico de de tal forma que a partir de pode descodificar o valor de . A composição de é necessária para estar em nossa classe. Além disso, qualquer adequada -coloring de pode ser convertido em um divisor adequada de . Isso pode ser feito, por exemplo, escrevendo um CNF que descreva se um dado codificado em binário como divide um fixo (que também possuiG ( N ) G ( N ) N N G ( N ) 3 G ( N ) d N d x 1 … x n N n 3 x i d $N$$G(N)$$G(N)$$N$$N$$G(N)$$3$$G(N)$$d$$N$$d$$x_1\ldots x_{n}$$N$$n$dígitos em binário, mas essas não são variáveis). Da satisfação de um CNF, há uma redução padrão para 3-COLORABILITY, de modo que você pode converter facilmente uma cor apropriada volta em uma tarefa que satisfaça . Assim, resolvendo o problema de coloração, você encontraria um divisor . Além disso, adicionando alguns gadgets extras simples, você também pode decidir se um gráfico tem esse formato ou não. Nossa classe é formada por gráficos criados dessa maneira, que são todos com cores.$3$$x_i$$d$$3$