Estou procurando exemplos de problemas parametrizados por um número , onde a dureza do problema não é monotônica em . A maioria dos problemas (na minha experiência) tem uma transição monofásica, por exemplo, -SAT possui uma transição monofásica de (onde o problema está em P) para (onde o problema é NP- completo). Estou interessado em problemas em que há transições de fase em ambas as direções (de fácil para difícil e vice-versa) à medida que aumenta.
Minha pergunta é um pouco semelhante à feita em Hardness Jumps in Computational Complexity , e de fato algumas das respostas são relevantes para minha pergunta.
Exemplos que eu conheço:
- -colorability de gráficos planares: em P, exceto quando , onde está NP-completo.
- Árvore de Steiner com terminais : em P, quando (cai para o menor caminho - ) e quando (cai para MST), mas NP é difícil "no meio". Não sei se essas transições de fase são nítidas (por exemplo, P para mas NP-difícil para ). Além disso, as transições de dependem do tamanho da instância de entrada, diferentemente dos meus outros exemplos.
- Contando atribuições satisfatórias de um módulo de fórmula planar : Em P quando é um número
primo deMersenne e # P-completo para amaioria (?) /Todos os outros valores de (de Aaron Sterling neste tópico ) . Muitas transições de fase! - Detecção de subgráfico induzido: o problema não é parametrizado por um número inteiro, mas por um gráfico. Existem gráficos (onde denota um certo tipo de relação de subgráfico), para o qual determinar se para um dado gráfico está em P para mas NP- completo para . (de Hsien-Chih Chang no mesmo tópico ).
Respostas:
Um campo com muita não monotonicidade da complexidade do problema é o teste de propriedades. Seja o conjunto de todos os gráficos n -vertex e chame P ⊆ G n uma propriedade de gráfico. Um problema genérico é determinar se um gráfico G tem a propriedade P (ou seja, G ∈ P ) ou está longe de ter a propriedade P em algum sentido. Dependendo do que P é e que tipo de acesso à consulta você tem no gráfico, o problema pode ser bastante difícil.Gn n P⊆Gn G P G∈P P P
Mas é fácil perceber que o problema não é monótono, pois se temos , o fato de P ser facilmente testável não implica que S seja facilmente testável ou que T seja.S⊂P⊂T P S T
Para ver esta, é o suficiente para observar que e P = ∅ são ambos trivialmente testável, mas que, para algumas propriedades, existem fortes limites inferiores.P=Gn P=∅
fonte
Para um dado gráfico e um número inteiro k ≥ 1 , a k- ésima potência de G , denotada por G k , tem o mesmo conjunto de vértices, de modo que dois vértices distintos são adjacentes em G k se a distância em G for no máximo k . O problema de k- ésima potência do gráfico dividido pergunta se um determinado gráfico é a k- ésima potência de um gráfico dividido.G k≥1 k G Gk Gk G k k k
fonte
A questão relacionada é discutida aqui .
fonte
Determinando se um gráfico tem uma camarilha dominante para:G
O caso é devido a Brandstädt e Kratsch , e o caso é observado em um artigo recente meu .d i a m ( G ) = 2diam(G)=3 diam(G)=2
fonte
Este é um exemplo do fenômeno que você está procurando?
Considere o problema do k-Clique, em que k é o tamanho da camarilha que estamos procurando. Portanto, o problema é "Existe um clique do tamanho k no gráfico G nos n vértices?"
Para todas as constantes k, o problema está em P. (O algoritmo de força bruta é executado no tempo .) Para valores grandes de k, por exemplo valores como n / 2, é NP completo. Quando k se aproxima muito de n, como nc para alguma constante c, o problema está em P novamente, porque podemos pesquisar todos os subconjuntos de n vértices de tamanho nc e verificar se algum deles forma um clique. (Existem apenas desses subconjuntos, que são polinomialmente grandes quando c é uma constante.)O ( n c )O(nk) O(nc)
fonte
Aqui está um exemplo que pode ser do tipo que você está procurando. O parâmetro não é um número inteiro, é um par de números. (Embora um deles possa ser corrigido para torná-lo um problema de um parâmetro).
O problema é avaliar o polinômio de Tutte de um gráfico G nas coordenadas (x, y). Podemos restringir as coordenadas para serem inteiros. O problema está em P se (x, y) é um dos pontos (1, 1), (-1, -1), (0, -1), (-1,0) ou é satisfatório (x-1 ) (y-1) = 1. Caso contrário, é # P-difícil.
Eu peguei isso no artigo da Wikipedia sobre o polinômio Tutte .
fonte
E a questão de calcular a permanente de uma matriz módulo ? Para isso é fácil (já que permanente = determinante) e Valiant (em " A complexidade de calcular o permanente ") mostrou que pode ser calculado o módulo no tempo para por uma variante modificada da eliminação gaussiana. Mas para que não é uma potência de , é UP-Hard. k = 2 2 d O ( n 4 d - 3 ) d ≥ 2 k 2k k=2 2d O(n4d−3) d≥2 k 2
fonte
Outro problema com esse fenômeno é o problema MÍNIMO -SPANNER em gráficos divididos.t
Para uma constante , um -spanner de um gráfico conectado é um spanning subgráfico conectado de tal que, para cada par de vértices e , a distância entre e em é na maioria vezes a sua distância em . O problema MINIMO -SPANNER solicita uma chave com número mínimo de arestas de um determinado gráfico.t G H G x y x y H t G t tt t G H G x y x y H t G t t
Um gráfico dividido é um gráfico cujo conjunto de vértices pode ser particionado em um clique e em um conjunto independente.
No presente documento , foi demonstrado que o mínimo de 2-INGLESA em gráficos de divisão é NP-duro, enquanto para cada , MÍNIMO -SPANNER é fácil de gráficos de divisão.tt≥3 t
fonte
Um exemplo bem conhecido é a coloração edge.k
É decidível em tempo polinomial se caso contrário, ele é completo .N Pk≠Δ NP
Para gráficos cúbicos, decidindo a existência de coloração de arestas usando:
Holyer, Ian (1981), "The NP-completeness of edge-colouring", SIAM Journal on Computing 10: 718–720
http://en.wikipedia.org/wiki/Edge_coloring
fonte
Este é um exemplo interessante (e surpreendente) para uma transição de fase P NP-difícil P NP-difícil :→ → → →⋯
Decidir se um gráfico completo em vértices, no qual cada vértice tem uma classificação estrita de todos os outros vértices, admite que uma correspondência popular seja em P para ímpar e NP-difícil para par . (O parâmetro é o número do vértice .)n n n n
A prova foi anunciada neste artigo .
fonte
Um caminho em um gráfico colorido de borda é arco - íris se nenhuma cor aparecer duas vezes nele. Um gráfico é colorido do arco - íris se houver um caminho do arco-íris entre cada par de vértices. Permita que RAINBOW- -COLORABILITY seja o problema de decidir se um determinado gráfico pode ser colorido em arco-íris usando cores.kk k
Para qualquer gráfico , o problema é fácil para pois é igual a verificar se é um gráfico completo. Para gráficos divididos , o problema é completo para e em para todos os outros valores de .k = 1 G N P k ∈ { 2 , 3 } P kG k=1 G NP k∈{2,3} P k
Veja Chandran, L. Sunil, Deepak Rajendraprasad e Marek Tesař. "Coloração arco-íris de gráficos divididos". pré-impressão do arXiv arXiv: 1404.4478 (2014).
fonte
Um subconjunto de um gráfico é um cutset desconectado se e estiverem desconectados.G G [ U ] G - UU⊆V(G) G G[U] G−U
Decidir se um gráfico de diâmetro 1 tem um cutset desconectado é trivial. O problema torna-se NP-difícil nos gráficos de diâmetro 2, veja este artigo e é novamente fácil nos gráficos de diâmetro, pelo menos 3, veja este artigo .
fonte