Classe de complexité correspondant au tri

Les algorithmes et la complexité sont deux parties de TCS. Je dirai simplement que les algorithmes sont l'étude des limites supérieures, montrant que vous pouvez faire quelque chose (avec des ressources limitées données), et la complexité consiste à montrer que vous ne pouvez pas le faire sans quelques ressources minimales.

Si souvent, un problème algorithmique est énoncé dans un modèle de décision afin de le placer dans une classe de complexité.

Mais quelque chose qui m'a toujours dérangé, c'est que certains algorithmes élémentaires ne sont jamais mentionnés comme appartenant à une classe particulière. Un exemple est le tri (de comparaison). Essayez comme je pourrais, une classe pertinente semble juste trop déficiente (vraiment, est-ce juste de vérifier dans l'espace de journalisation que le résultat est trié? Cela semble juste trop faible, ou je ne reçois pas la bonne version de décision).

Quelle est la classe de complexité la meilleure / la plus appropriée / la plus utile dans laquelle se situe le tri par comparaison?

cc.complexity-theory sorting Mitch
la source

Réponses:

Le problème de tri est en fait complet pour $\mathsf{TC}^0$ (sous réduction). Une source standard pour cela est la section 1.4.3 du livre de Vollmer . $\mathsf{AC}^0$

Notez que est la classe des problèmes de décision, mais nous pensons généralement au tri comme un problème de fonction, c'est-à-dire que nous voulons afficher les nombres, par exemple, dans un ordre non décroissant. Cependant, nous pouvons également définir le tri comme un problème de décision comme suit: $\mathsf{TC}^0$

Étant donné une séquence de nombres et deux nombres , nous voulons décider si est à la position dans la séquence que nous obtenons en triant en non décroissante commande. Notez que pour éviter toute ambiguïté, lorsque , nous voulons précède si . $a_1,\ldots,a_n$ $k,p\in [n]$ $a_k$ $p$ $a_1,\ldots,a_n$ $a_i=a_j$ $a_i$ $a_j$ $i<j$

Dai Le
la source

Excellent ... spécifié comme quel problème de décision formel?

Mitch

Il serait double excellent d'inclure une référence dans votre réponse.

Oleksandr Bondarenko

@Mitch et @Okeksandr: Merci pour vos commentaires! Je viens de prolonger ma réponse pour clarifier ces points.

Dai Le

Cela ressemble au problème de décision pour les statistiques de commande. Y a-t-il un problème connexe où tout est à sa place? Quelque chose comme une séquence donnée d'

et une permutation

sur

, décide si

. C'est aussi dur que le vôtre; est-ce plus difficile ou complet pour une classe incluse?

a_{1} . . . a_{n}

$a_1...a_n$

σ

$\sigma$

[1.. n]

$[1..n]$

\forall_{1 \leq k < j \leq n}, a_{σ_{k}} < a_{σ_{j}}

$\forall_{1\le k\lt j\le n}, a_{\sigma_k} < a_{\sigma_j}$

Mitch

@Mitch: Je pense qu'il est plus facile de vérifier si tout est bien au bon endroit que de trier. L'intuition est que vous pouvez vérifier que

pour toute la paire possible

avec

en parallèle, ce qui, je crois, peut être fait dans

. Pour le problème de tri ci-dessus, vous devez pouvoir "compter" pour déterminer la bonne position d'un nombre dans l'ordre linéaire.

a_{σ_{k}} < a_{σ_{j}}

$a_{\sigma_k}<a_{\sigma_j}$

(a_{σ_{k}}, a_{σ_{j}})

$(a_{\sigma_k},a_{\sigma_j})$

k < j

$k<j$

{A C}^{0}

$\mathsf{AC}^0$

Dai Le

Je crois que FP est ce que vous recherchez.

Nicholas Mancuso
la source

Eh bien, je suis plutôt à la recherche de la classe de complexité de décision pertinente plutôt que de la classe fonctionnelle, mais même ainsi, je suis assez certain que le tri par comparaison n'est pas proche de P-complet (ou FP-complet), donc je m'attends à une classe plus petite pour laquelle il devrait être inclus / complet.

Mitch

Je ne savais pas que l'exhaustivité était l'une des exigences de votre question. En tant que problème de décision (si vous ne tenez pas compte de votre contrainte d'exhaustivité), pourquoi P ne serait-il pas acceptable comme réponse? Étant donné un DTM, vous pouvez à la fois produire et valider un certificat en temps polynomial.

Nicholas Mancuso

Étant donné un problème général, ce que je veux généralement savoir, ce n'est pas seulement que c'est le temps polynomial, mais la plus petite classe dans laquelle il pourrait être. J'aimerais savoir si c'est en LOGCFL, NL, L, AC_0, etc. est une façon de faire mieux. Donc, ce n'est pas une exigence de ma question, mais une chose susceptible d'être dans une réponse.

Mitch