Quais são as relações entre essas hipóteses na teoria da complexidade refinada?

23

A teoria da complexidade, através de conceitos como NP-completeness, distingue entre problemas computacionais que têm soluções relativamente eficientes e aqueles que são intratáveis. A complexidade "refinada" visa refinar essa distinção qualitativa em um guia quantitativo sobre o tempo exato necessário para resolver problemas. Mais detalhes podem ser encontrados aqui: http://simons.berkeley.edu/programs/complexity2015

Aqui estão algumas hipóteses importantes:

ETH: - requer tempo para alguns .3SAT δ > 02δnδ>0

SETH: para cada , existe um tal que - em variáveis, cláusulas não podem ser resolvidas em .ε>0kkSATnm2(1ε)n poly m

Sabe-se que SETH é mais forte que ETH e ambos são mais fortes que e ambos mais fortes que .PNPFTPW[1]

Quatro outras conjecturas importantes:

  1. Conjectura 3SUM: 3SUM em números inteiros em requer tempon{n3,,n3}n2o(1)

  2. Conjectura OV: vetores ortogonais em vetores requerem tempo.nn2o(1)

  3. APSP conjectura: Todos pares Caminho Mais Curto em nodos e picaram pesos requer tempo.O ( log n ) n 3 - o ( 1 )nO(logn)n3o(1)

  4. Conjectura BMM: Qualquer algoritmo "combinatório" para multiplicação de matrizes booleanas requer tempo .n3o(1)

Sabe-se que SETH implica a conjectura OV (Ryan Willams, 2004). Além da prova de Ryan de que SETH OV Conjecture, não há outras reduções relacionadas às conjecturas conhecidas.

Minha pergunta: você conhece outras hipóteses ou conjecturas relacionadas nessa área? Quais são as relações entre eles?

Agradecimentos: os resultados listados são dos slides de Virginia Vassilevska Williams, ela também me deu respostas parciais para essa pergunta.

Link para slides: http://theory.stanford.edu/~virgi/overview.pdf

Rupei Xu
fonte
Olá Rupei, tenho trabalhado em vários problemas de acessibilidade e restrição de gráficos que estão relacionados à lista muito agradável de problemas de complexidade refinada que você mencionou. Se você estiver interessado, envie-me um e-mail e poderemos conversar um dia. Fico feliz em ver outras pessoas interessadas em complexidade refinada no stackexchange. :)
Michael Wehar
3
Uma redução trivial: APSP subcúbica "combinatória" implica BMM subcúbica "combinatória". Para o 3SUM, consulte a relação entre problemas relacionados na página 14 deste slide cs.uwaterloo.ca/~tmchan/talks/bsg_stoc_talk.pdf . Para BMM, consulte a Seção G deste artigo theory.stanford.edu/~virgi/tria-mmult-conf.pdf . Para o APSP, existem muitos artigos de Virginia mostrando equivalência subcúbica.
Thatchaphol
1
@Thatchaphol, obrigado pelo compartilhamento!
Rupei Xu 21/09/2015

Respostas:

15

Este é um artigo recente que apresenta a Hipótese de Tempo Exponencial Forte Não Determinista (NSETH), que é uma extensão da SETH.

NSETH: Para cada , existe um tal que -DNF-TAUT não pode ser resolvido em tempo não determinístico .k k 2 ( 1 - ϵ ) nϵ>0kk2(1ϵ)n

NSETH implica SETH. Se NSETH for verdadeiro, alguns problemas não terão limites inferiores de SETH (porque eles têm algoritmos não determinísticos mais rápidos que algoritmos determinísticos).

Este artigo também introduziu a Hipótese de Tempo Exponencial Forte Não-determinística Não Uniforme (NUNSETH), uma hipótese mais forte que NSETH e SETH.

NUNSETH: Para cada , existe um tal que -DNF-TAUT não pode ser reconhecido por famílias de circuitos não determinísticas do tamanho .k k 2 ( 1 - ϵ ) nϵ>0kk2(1ϵ)n

Rosetta
fonte
1
Obrigado pelo trabalho pioneiro! Ryan Williams acredita que o SETH é falso. Você acha que NSETH é verdadeiro?
Rupei Xu 21/09/2015
2
Este artigo observa que Ryan realmente mostrou que a versão MA do SETH é falsa, o que parece sugerir que é improvável que o NSETH seja verdadeiro. No entanto, em certo sentido, o ponto é que, para mostrar conexões entre algumas dessas outras conjecturas, você primeiro precisa progredir na refutação do NSETH.
palindrome
8

Outra conjectura interessante é a dureza de Clique para fixo (veja aqui ).kkk

Esse não é exatamente o tipo de relacionamento que você está procurando, mas houve um artigo interessante do FOCS mostrando que um problema natural chamado "Triângulos correspondentes" é difícil sob qualquer uma das conjecturas SETH, 3SUM ou APSP (veja aqui ). Atualmente, não se sabe se alguma dessas três conjecturas implica ou não de uma maneira interessante - essa é uma das principais questões em aberto da Complexidade de Alta Qualidade.

GMB
fonte
1
Obrigado Greg! Minha motivação original para postar esta pergunta aqui é coletar todos os resultados existentes nessa área, como as boas coleções no Boletim de Notícias da Complexidade Parametrizada fpt.wikidot.com/…
Rupei Xu
O link -clique parece estar quebrado. Apenas pensei em avisar você. :)k
Michael Wehar
1

Resultados relativamente recentes de Backurs, Indyk aceitou no STOC 2015 que a distância de edição da computação em tempo → SETH falso vínculo é claramente / forte com o novo emergente programa / paradigma de pesquisa de "complexidade refinada". eles estão intimamente relacionados / baseados no resultado de Williams que SETH → Vetores ortogonais conjecturam. (mesmo coberto pela grande mídia, o Boston Globe).O(n2ϵ)

um resultado aparentemente muito semelhante, devido a Wehar, considera o problema do "vazio de interseção do 2 DFA" e considera que tempo → SETH é falso.O(n2ϵ)

Wehar tem outros resultados que também parecem se encaixar em conexões gerais de "complexidade refinada", que o mesmo vazio de interseção DFA no tempo →kno(k)NLP

nesse sentido, também vale a pena mencionar que existe uma conexão significativa conhecida entre construções DFA e cálculos de distância de Levenshtein, por exemplo, neste artigo

vzn
fonte
1
Adicionadas algumas pequenas correções ao seu post VZN. Foi legal da sua parte me mencionar. Sou muito apaixonado pelo problema de interseção do DFA e espero ter mais coisas para compartilhar no futuro. :)
Michael Wehar