L / P / PSpace vs P / NP

12

em 1979, Hopcroft / Ullman escreveu que o LPSP é conhecido como PSpace, mas o LPSP é a única contenção adequada (e trivial) conhecida, embora todos sejam conjecturados como contenções adequadas e "onde as coisas ainda estão" ~ 4 décadas depois .

desde então, existem conexões conhecidas entre L ⊊ P, P ⊊ PSpace e P ⊊ NP? todos eles ainda são considerados independentes ou existem sinais de alguma interdependência?

motivação: esta pergunta é parcialmente inspirado pelos recentes resultados Backurs-Indyk amarrando SETH para O (n 2 ) editar distância. SETH é tempo exponencial e a distância de edição é PTime. (e também de certa forma a questão de provar limites inferiores comprovando limites superiores )

vzn
fonte

Respostas:

8

LPSPACE

O trabalho recente sobre `` Complexidade refinada '', como o resultado da distância de edição de Backurs e Indyk, evita o fato de que não podemos provar contenções adequadas, como . Em particular, o SETH é muito mais forte conjectura que , afirmando mais ou menos que CNF-SAT requer tempo (não apenas tempo super-polinomial) .Nesta conjectura mais forte, se você pode mostrar uma redução de de CNF- SAT para problemas em (como Editar Distância), então você obtém um limite inferior condicional com base em SETH.Portanto, as distinções com as quais esses trabalhos se preocupam (por exemplo, vs.PNPPNP2n2n/kPΩ(nk)2n2(1δ)n) são muito mais restritas do que as distinções entre as classes de complexidade tradicionais mencionadas na postagem.

Da mesma forma, ao provar limites mais baixos do circuito, fornecendo algoritmos de satisfação mais rápidos, geralmente precisamos de aprimoramentos refinados sobre os algoritmos triviais para fornecer limites mais baixos. Por exemplo, um algoritmo para o CircuitSAT em circuitos de portas provaria .O(2n)2npoly(nk)/nω(1)nkNEXPP/poly

palíndromo
fonte
Como isso responde à pergunta, que pergunta sobre implicações (ou "interdependências", o que isso possa significar) entre três declarações?
András Salamon
Meu objetivo era responder a pergunta com base em sua motivação declarada. Não conheço pessoalmente nenhuma interdependência não trivial entre as declarações.
Palindrome