Problèmes qui nécessitent un temps quadratique

Je cherche des exemples de problèmes qui ont une borne inférieure de $\Omega(|x|^2$ ) pour l'entrée $x$ .

Le problème doit avoir les propriétés suivantes:

$\Omega(n^2)$ Preuve d'exécution pour tout algorithme - la première priorité est d'avoir un argument de limite inférieure aussi simple que possible.
$O(n^2)$ Algorithme , si possible, simple aussi.
Taille de sortie de $O(n)$ (ou inférieure). Évidemment, tout problème nécessitant une sortie de longueur $\Omega(n^2)$ nécessitait au moins un temps d'exécution similaire, mais ce n'est pas ce que je recherche. Notez que tout problème de décision convient ici.
(si possible) un problème "naturel". Sans définition formelle, un problème que tout diplômé CS reconnaîtrait est préférable.

On m'a récemment posé des questions sur un tel problème, mais je n'ai pas pu en trouver un simple. Le premier problème qui m'est venu à l'esprit était , qui a été conçu comme un problème d'exécution . Ce n'était pas assez simple et de plus, la conjoncture s'est récemment révélée fausse : o. $3SUM$ $\Omega(n^2)$

Aller à un problème extrêmement naturel, je crois que le problème qui obtient en entrée un TM déterministe et entrée et indique la position de la tête de bande après étapes quand il est courir sur répond probablement à la question. $\langle M \rangle,x$ $(|M|+|x|)^2$ $x$

Si vous en avez absolument besoin, admettons que nous utilisons le modèle TM à bande unique, bien que je préfère les problèmes dont l'exécution est indépendante du modèle exact (tant qu'il est raisonnable).

Alors, pouvons-nous trouver un problème simple (à prouver), naturel (bien connu) dont le temps d'exécution est ? $\Theta(n^2)$

Je pense que "étant donné les nombres naturels

, calculer

" se qualifie. Notez également cette question .

x

$x$

y

$y$

x + y

$x+y$

Raphael

La seule façon dont nous savons prouver les bornes inférieures super-linéaires sur les machines de Turing multitape est la diagonalisation. Pour les machines de Turing à bande unique, vous pouvez obtenir un peu mieux en utilisant des séquences de croisement, mais pas aussi loin que

sauf si vous restreignez peut-être l'espace.

n^{2}

$n^2$

Yuval Filmus

Voir ici pour une autre question connexe; l'inversion des entrées semble être un bon candidat.

Raphael

Je ne pense pas que vous puissiez le faire avec un problème de décision, car la borne inférieure la mieux trouvée pour NP est O (n).

Albert Hendriks

Merci pour votre commentaire @AlbertHendriks. Pouvez-vous s'il vous plaît partager une référence à une source / enquête affirmant que la borne inférieure la plus connue pour tout problème dans NP est

Ω (n)

$\Omega(n)$

Réponses:

Trouver une coupe de gâteau sans envie nécessite des requêtes . Cependant, cela ne répond pas directement à votre question car le modèle de calcul est différent d'une machine de Turing. $\Omega(n^2)$

Soit dit en passant, actuellement l' algorithme le plus rapide connu pour ce problème nécessite requêtes, il y a donc un écart énorme par rapport à la borne inférieure - probablement l'un des plus grands écarts en informatique. $n^{n^{n^{n^{n^{n}}}}}$

Erel Segal-Halevi
la source

Comme dans le lien fourni par Raphael, Peter montre que l'inversion d'entrée nécessite $\Theta(n^2)$ temps sur les MT à bande unique vanille. Pour un problème de décision, le langage

L = {x 0^{| x |} x ∣ x \in {0, 1}^{*}}

$L = \{x0^{|x|}x \mid x \in \{0,1\}^\ast \}$ aussi prouvable a besoin

Θ (n^{2})

$\Theta(n^2)$ le temps de calcul. Pour voir cela, utilisez l'argument de complexité de la communication de Peter, ainsi qu'un résultat classique dont

E Q_{n}

$EQ_n$ besoin

Θ (n)

$\Theta(n)$ bits de communication, pour afficher la limite inférieure quadratique de

L

$L$ . L'approche similaire fonctionne pour une approche plus naturelle

L = {x x ∣ x \in {0, 1}^{*}}

$L = \{xx \mid x \in \{0,1\}^\ast \}$ .

Soit dit en passant, il convient de mentionner que la "méthode de la séquence de croisement" mentionnée par Yuval est (à ma connaissance) mathématiquement équivalente (ou, peut-être, inforior) à celle de la complexité de la communication.

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

Lwins
la source