Existe um problema natural no tempo quase polinomial, mas não no tempo polinomial?

21

László Babai provou recentemente que o problema do isomorfismo gráfico está no tempo quase-polinomial . Veja também sua palestra na Universidade de Chicago, nota das palestras de Jeremy Kun pós 1 da GLL , pós 2 da GLL , pós 3 da GLL .

De acordo com o teorema de Ladner, se PNP , em seguida, NPI não está vazia, isto é, NP contém problemas que não são em P ou NP -completo. No entanto, a linguagem construída por Ladner é artificial e não é um problema natural. Nenhum problema natural é conhecido por ser em NPI mesmo condicionalmente sob PNP . Mas alguns problemas são acreditados para ser bons candidatos para NPI , tais como números inteiros factoring e GI.

Podemos pensar que, com o resultado de Babai, pode haver um algoritmo de tempo polinomial para GI. Muitos especialistas acreditam que NPQP=DTIME(npolylogn) .

Existem alguns problemas para os quais conhecemos algoritmos de tempo quase polinomial, mas nenhum algoritmo de tempo polinomial é conhecido. Tais problemas surgem em algoritmos de aproximação; Um exemplo famoso é o problema direcionado da árvore de Steiner, para o qual existe um algoritmo de aproximação de tempo quase polinomial, atingindo uma razão de aproximação de O(log3n) ( n sendo o número de vértices). No entanto, mostrar a existência de um algoritmo polinomial de tempo é um problema em aberto.

Minha pergunta:

Conhecemos algum problema natural que esteja em QP mas não em P ?

Rupei Xu
fonte
6
O teorema da hierarquia do tempo não garante a existência de tais problemas?
RB
@RB Obrigado pela sua resposta. Você acredita que a hierarquia de tempo pode entrar em colapso? Estou esperando alguns exemplos naturais que podem ser resolvidos em tempo quase polinomial, mas não em tempo polinomial.
Rupei Xu
3
@RupeiXu É um fato conhecido que não pode entrar em colapso.
Tom van der Zanden
3
@RupeiXu Sua pergunta seria interessante se você estiver procurando por um problema natural .
Mohammad Al-Turkistany
3
O conjunto mínimo de domínio nos torneios está no QP. Não pode estar em P, a menos que o ETH seja falso.
Mohammad Al-Turkistany

Respostas:

25

De fato, tem havido muitos trabalhos recentes sobre a comprovação do tempo de execução quase polinomial mais baixo para problemas computacionais, principalmente com base na hipótese de tempo exponencial. Aqui estão alguns resultados para problemas que considero bastante naturais (todos os resultados abaixo dependem do ETH):

  • Aaronson, Impagliazzo e Moshkovitz [1] mostram um tempo quase polinomial mais baixo para problemas de satisfação de restrições densas (CSPs). Observe que a maneira como o CSP é definido neste documento permite que o domínio seja polinomialmente grande, como é sabido que o caso em que o domínio é pequeno possui um PTAS.

  • Braverman, Ko e Weinstein [2] provar um tempo de semi-polinomial limite inferior para encontrar -best ε -approximate Nash equilíbrio, o que corresponde ao algoritmo de Lipton et al. [3].ϵϵ

  • Braverman, Ko, Rubinstein e Weinstein [4] mostram um tempo de semi-polinomial limite inferior para aproximar mais densa -subgraph com perfeita plenitude (ou seja dado um gráfico que contém uma k -clique, encontra um subgráfico de tamanho k que é ( 1 - ε ) -dense por alguma pequena constante ε ). Novamente, existe um algoritmo de tempo quase polinomial para o problema (Feige e Seltser [5]).kkk(1ϵ)ϵ

Referências

  1. Sou com vários Merlins. In Computational Complexity (CCC), 29ª Conferência IEEE de 2014, páginas 44–55, junho de 2014.

  2. Mark Braverman, Young Kun Ko e Omri Weinstein. Aproximar o melhor equilíbrio nash em -time quebra a hipótese de tempo exponencial. Em Anais do Vigésimo Sexto Simpósio Anual da ACM-SIAM sobre Algoritmos Discretos, SODA '15, páginas 970–982. SIAM, 2015.no(logn)

  3. Richard J. Lipton, Evangelos Markakis e Aranyak Mehta. Jogando jogos grandes usando estratégias simples. Em Anais da 4ª Conferência da ACM sobre Comércio Eletrônico, EC '03, páginas 36–41, Nova York, NY, EUA, 2003. ACM.

  4. Mark Braverman, Young Kun-Ko, Aviad Rubinstein e Omri Weinstein. Dureza ETH para o Densest- Subgraph com perfeita perfeição. Colóquio Eletrônico sobre Complexidade Computacional (ECCC), 22:74, 2015.k

  5. U. Feige e M. Seltser. Nos problemas mais densos do sub-gráfico . Relatório técnico, 1997.k

Pasin Manurangsi
fonte
22

Megido e Vishkin provou que mínima conjunto dominante em torneios está em . Eles mostraram que o conjunto dominante do torneio possui um algoritmo de tempo P, se o SAT tiver um algoritmo de tempo subexponencial. Portanto, o problema do conjunto dominante do torneio não pode estar em P , a menos que o ETH seja falso.QPP

NPNP

nlogn0

Mohammad Al-Turkistany
fonte
10

A dimensão VC da computação parece improvável em tempo polinomial, mas possui um algoritmo de tempo quase-polinomial.

O(logn)

Joe Bebel
fonte
7

Se a hipótese do tempo exponencial estiver correta (ou mesmo versões mais fracas), não será possível resolver o 3SAT para instâncias com número poliglogado de variáveis ​​no tempo polinomial. Obviamente, o tempo quase polinomial pode resolver esses casos prontamente.

T(n)lognT(n)T(n)

Sariel Har-Peled
fonte
4

Foi mostrado recentemente que a solução de jogos de paridade está no QP: https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf

μ

NPcoNPUPcoUP

No entanto, o artigo recente acima deu um salto significativo para o QP. Ainda não se sabe se esses jogos estão em P.

Shaull
fonte
2

Em algoritmos clássicos, decaimento de correlação e zeros complexos de funções de partição de sistemas quânticos de muitos corpos por Aram Harrow, Saeed Mehraban e Mehdi Soleimanifar

um algoritmo clássico de tempo quase polinomial que estima a função de partição de sistemas quânticos de muitos corpos a temperaturas acima do ponto de transição da fase térmica

foi apresentado.

Não se pode dizer muito aqui sobre a parte "mas não no tempo polinomial" da questão. Pode até ser provável que um algoritmo de tempo polinomial seja encontrado posteriormente, dado o histórico do trabalho anterior, veja abaixo.

Como a "estimativa da função de partição" está relacionada aos algoritmos de aproximação? Trabalho anterior (p. 11):

Há uma recente abordagem conceitualmente diferente para estimar a função de partição, que é a base deste trabalho. Essa abordagem visualiza a função de partição como um polinômio de alta dimensão e usa a expansão de Taylor truncada para estender a solução em um ponto computacionalmente fácil para um regime não trivial de parâmetros. Desde sua introdução [Bar16a], este método tem sido utilizado para obter algoritmos determinísticos para vários problemas interessantes, como os modelos Ising ferromagnéticos e antiferromagnéticos [LSS19b, PR18] em gráficos limitados.

inclui

[LSS19b] Jingcheng Liu, Alistair Sinclair e Piyush Srivastava. A função de partição Ising: zeros e aproximação determinística. Journal of Statistical Physics, 174 (2): 287–315, 2019. arXiv: 1704.06493

que menciona o seguinte na seção sobre trabalhos relacionados:

Em uma linha paralela de trabalho, Barvinok iniciou o estudo da aproximação de Taylor do logaritmo da função de partição, o que levou a algoritmos de aproximação de tempo quase-lipinomiais para uma variedade de problemas de contagem [6, 7, 9, 10]. Mais recentemente, Patel e Regts [41] mostraram que para vários modelos que podem ser escritos como somas de subgráficos induzidos, é possível obter um FPTAS a partir dessa abordagem.

V. Patel e G. Regts. Algoritmos determinísticos de aproximação em tempo polinomial para funções de partição e polinômios gráficos. SIAM J. Comput., 46 (6): 1893–1919, dezembro de 2017. arXiv: 1607.01167

Em conclusão, "estimar a função de partição" está intimamente relacionado aos algoritmos de aproximação, e existem algoritmos de aproximação de tempo quase-polinomiais para uma variedade de problemas de contagem, e para alguns desses FPTAS foram obtidos. De modo geral, essa classe de problemas relacionados à função de partição parece produzir algoritmos de aproximação de tempo quase-polinomial, mas muitas vezes as melhorias posteriores atingem o tempo polinomial.

Thomas Klimpel
fonte