Problemas que provavelmente requerem tempo quadrático

Estou procurando exemplos de problemas que tenham um limite inferior de ) para a entrada x .$\Omega(|x|^2$$x$

O problema precisa ter as seguintes propriedades:

1. prova de tempo de execução para qualquer algoritmo - primeira prioridade é ter o mais simples possível argumento limite inferior.$\Omega(n^2)$
2. Algoritmo O ( n 2 ) , se possível, também simples.$O(n^2)$
3. Tamanho de saída de (ou menor). Obviamente, qualquer problema que exija Ω ( n 2 ) de saída prolongada requer pelo menos tempo de execução semelhante, mas não é isso que estou procurando. Observe que qualquer problema de decisão se encaixa aqui.$O(n)$$\Omega(n^2)$
4. (se possível) um problema "natural". Sem uma definição formal, é preferível um problema que qualquer graduado em CS reconheça.

Recentemente, fui perguntado sobre esse problema, mas não consegui encontrar um problema simples. O primeiro problema que veio à mente foi o , que foi conjurado para ser um problema de tempo de execução Ω ( n 2 ) . Isso não foi suficientemente simples e, além disso, a estrutura foi recentemente provada falsa : o.$3SUM$$\Omega(n^2)$

Indo para um problema extremamente antinatural, eu acredito que o problema que recebe como entrada uma TM determinista e entrada , e envia a posição da cabeça da fita depois ( | M | + | x | ) 2 etapas quando é rodar em x provavelmente responde à pergunta.$\langle M \rangle,x$$(|M|+|x|)^2$$x$

Se for absolutamente necessário, vamos concordar que estamos usando o modelo TM de fita única, embora eu prefira problemas cujo tempo de execução seja independente do modelo exato (desde que seja razoável).

Então, podemos encontrar um problema simples (para provar), natural (bem conhecido), cujo tempo de execução é ?$\Theta(n^2)$

Encontrar um corte de bolo sem inveja requer consultas. No entanto, isso não responde diretamente à sua pergunta, pois o modelo computacional é diferente de uma máquina de Turing.$\Omega(n^2)$

A propósito, atualmente o algoritmo conhecido mais rápido para esse problema requer consultas, portanto há uma enorme lacuna no limite inferior - provavelmente uma das maiores lacunas na ciência da computação.$n^{n^{n^{n^{n^{n}}}}}$

$\Theta(n^2)$

A propósito, vale ressaltar que o "método da sequência de cruzamento" mencionado por Yuval é (pelo meu conhecimento) matematicamente equivalente (ou, talvez, inforior) à complexidade da comunicação.

$\mathsf{SAT}$$O(n^{2 \cos(\pi/7)})$ $n^{o(1)}$$2 \cos(\pi/7) \approx 1.8$