A classe de complexidade consiste naqueles N P -Problemas que podem ser decididas por um máquina de Turing não-determinístico tempo polinomial que tem no máximo uma aceitar caminho computacional. Ou seja, a solução, se houver, é única nesse sentido. É altamente improvável que todos os problemas de estejam em , porque pelo Teorema de Valiant-Vazirani isso implicaria o colapso .P N P = R P
Por outro lado, nenhum -problem é conhecido por ser N P -completo, o que sugere que o requisito solução única ainda de alguma forma torna mais fácil.
Estou procurando exemplos, onde a suposição de exclusividade leva a um algoritmo mais rápido.
Por exemplo, observando os problemas do gráfico, uma clique máxima em um gráfico pode ser encontrada mais rapidamente (embora ainda esteja em tempo exponencial), se soubermos que o gráfico possui uma clique máxima exclusiva ? Que tal a capacidade única , o caminho hamiltoniano único, o conjunto mínimo dominante exclusivo etc.?
Em geral, podemos definir uma versão de solução única de qualquer problema -completo, escalando-os para U P . É conhecido por algum deles que adicionar a suposição de exclusividade leva a um algoritmo mais rápido? (Permitindo que ainda permaneça exponencial.)
fonte
Respostas:
3-SAT pode ser um desses problemas. Atualmente, o melhor limite superior para o Unique 3-SAT é exponencialmente mais rápido do que para o 3-SAT geral. (A aceleração é exponencial, embora a redução no expoente seja pequena.) O recordista do caso único é este artigo de Timon Hertli.
O algoritmo de Hertli baseia-se no importante algoritmo PPSZ de Paturi, Pudlák, Saks e Zane para -SAT, que eu acredito que ainda seja o mais rápido para k ≥ 5 (consulte também este artigo da enciclopédia). A análise original mostrou limites melhores para o k- SAT único do que para o k- SAT geral quando k = 3 , 4 ; posteriormente, no entanto, Hertli mostrou em outro artigok k≥5 k k k=3,4 que você pode obter os mesmos limites para o algoritmo PPSZ (ligeiramente ajustado), sem assumir a exclusividade. Portanto, talvez a singularidade ajude, e possa definitivamente simplificar a análise de alguns algoritmos, mas nossa compreensão do papel da singularidade para o -SAT ainda está crescendo.k
Há evidências de que o -SAT exclusivo não é muito mais fácil do que o k -SAT geral . A forte exponencial Tempo hipótese (Seth) afirma que não existe δ < 1 de tal modo que n -variável k -SAT é solúvel em ó * ( 2 δ n ) de tempo para cada constante k ≥ 3 . Foi mostrado em um artigo de Calabro, Impagliazzo, Kabanets e Paturi que, se o SETH for válido, a mesma afirmação é verdadeira para o Unique k -SAT. Além disso, se k geralk k δ<1 n k O∗(2δn) k≥3 k k -SAT requer tempo exponencial, ou seja, existe algum modo que o k- SAT geral não possa ser resolvido no tempo O ∗ ( 2 ϵ n ) , então o mesmo deve ser verdadeiro para o exclusivo 3-SAT. Veja o documento para a declaração mais geral. k≥3,ϵ>0 k O∗(2ϵn)
(Nota: o notação suprime factores polinomiais no comprimento de entrada).O∗
fonte
O menor problema de trajetória independente de 2-vértices em gráficos não direcionados recentemente resolvidos (ICALP14) por A. Bjorklund e T. Husfeldt. Mas a solução determinística é para o caso da existência de uma solução única. No caso de haver mais de uma solução, eles mostraram que o problema pertence ao RP . Como autores do artigo mencionado, não se sabe se o problema está em P no cenário geral.
fonte
Fora da teoria da complexidade e da análise de algoritmos, a suposição de que pode haver apenas uma solução forma a base de algumas das regras padrão usadas para deduzir a solução nos quebra-cabeças do Sudoku. Essas regras geralmente envolvem a busca de maneiras pelas quais partes do quebra-cabeça possam ter duas ou mais soluções que não interagem com o restante do quebra-cabeça. Isso não pode acontecer na solução real; portanto, se um padrão que ameaça causar isso for encontrado, ele deverá ser quebrado, permitindo que o solucionador deduza restrições sobre a aparência da solução real. Consulte http://www.brainbashers.com/sudokuuniquerectangles.asp para obter alguns exemplos de regras de dedução baseadas na exclusividade.
fonte
A suposição de uniqeness significa que a paridade do número de Ham. caminhos é o mesmo que decidir se o gráfico é hamiltoniano.
fonte