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 )