Limites inferiores da troca espaço-tempo

Após a discussão sobre limites mais baixos para o 3SAT [ 1 ], estou pensando quais são os principais resultados de limites inferiores formulados como trocas no espaço-tempo. Estou excluindo resultados como, por exemplo, o teorema de Savitch; uma boa entrada focaria em um único problema e seus limites. Um exemplo seria:

"Seja T e S o tempo de execução e o espaço vinculado a qualquer algoritmo SAT. Então devemos ter T⋅S≥n2cos (π / 7) −o (1) infinitamente frequentemente." (Dado em [ 1 ] por Ryan Williams.)

ou

"O SAT não pode ser resolvido simultaneamente no tempo n ^{1 + 0 (1)} e no espaço n ^1-ε para qualquer ε> 0 em máquinas de Turing não determinísticas de acesso aleatório geral." (Lance Fortnow em 10.1109 / CCC.1997.612300)

Além disso, estou incluindo definições de classes de complexidade de troca de espaço-tempo natural (excluindo classes de circuito).

Aqui estão algumas referências adicionais. Pode-se encontrar mais olhando os documentos que os citam.

$P$$T^2 S \geq \Omega(n^3)$

$O(n)$$O(1)$$k+1$$T S \geq \Omega(n^2)$$k$

$S \leq o(n)$$T \geq \omega(n)$

$TS \geq \Omega(n^2)$