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 , em seguida, não está vazia, isto é, contém problemas que não são em ou -completo. No entanto, a linguagem construída por Ladner é artificial e não é um problema natural. Nenhum problema natural é conhecido por ser em mesmo condicionalmente sob . Mas alguns problemas são acreditados para ser bons candidatos para , 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 .
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 ( 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 mas não em ?
Respostas:
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]).k k k (1−ϵ) ϵ
Referências
Sou com vários Merlins. In Computational Complexity (CCC), 29ª Conferência IEEE de 2014, páginas 44–55, junho de 2014.
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)
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.
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
U. Feige e M. Seltser. Nos problemas mais densos do sub-gráfico . Relatório técnico, 1997.k
fonte
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.QP P
fonte
A dimensão VC da computação parece improvável em tempo polinomial, mas possui um algoritmo de tempo quase-polinomial.
fonte
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.
fonte
Foi mostrado recentemente que a solução de jogos de paridade está no QP: https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf
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.
fonte
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
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):
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:
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.
fonte