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

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 .$3$$SAT$ δ > $2^{\delta n}$$\delta > 0$

SETH: para cada , existe um tal que - em variáveis, cláusulas não podem ser resolvidas em .$\varepsilon > 0$$k$$k$$SAT$$n$$m$$2^{(1-\varepsilon)n}~poly~m$

Sabe-se que SETH é mais forte que ETH e ambos são mais fortes que e ambos mais fortes que .$P \neq NP$$FTP\neq W[1]$

Quatro outras conjecturas importantes:

1. Conjectura 3SUM: 3SUM em números inteiros em requer tempo$n$$\{-n^3,…,n^3\}$$n^{2-o(1)}$

2. Conjectura OV: vetores ortogonais em vetores requerem tempo.$n$$n^{2-o(1)}$

3. APSP conjectura: Todos pares Caminho Mais Curto em nodos e picaram pesos requer tempo.O ( log n ) n 3 - o ( 1 $n$$O(\log n)$$n^{3-o(1)}$

4. Conjectura BMM: Qualquer algoritmo "combinatório" para multiplicação de matrizes booleanas requer tempo .$n^{3-o(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.$\implies$

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

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 - ϵ ) $\epsilon >0$$k$$k$$2^{(1-\epsilon)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 - ϵ ) $\epsilon >0$$k$$k$$2^{(1-\epsilon)n}$

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

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.

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(n^{2-\epsilon})$

• A distância de edição não pode ser calculada em tempo fortemente subquadrático (a menos que SETH seja falso) / Backurs, Indyk

• Um novo mapa traça os limites da computação / Pavlus, revista Quanta

• Por 40 anos, os cientistas da computação procuraram uma solução que não existe / Boston Globe

• Evidência intrigante / RJLipton blog

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(n^{2-\epsilon})$

• Decidir o vazio da interseção de idiomas regulares em tempo subquadrático / história SE

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 →$k$$n^{o(k)}$$NL \subsetneq P$

• Resultados de dureza para não vazamento / Wehar de interseção

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

• Correção rápida de cordas com autômatos Levenshtein / Shulz, Mihov