Des problèmes non triviaux résolubles en temps constant?

Le temps constant est la complexité absolue la plus basse. On peut se demander: y a-t-il quelque chose de non trivial qui peut être calculé en temps constant? Si nous nous en tenons au modèle de la machine de Turing, alors peu de choses peuvent être faites, car la réponse ne peut dépendre que d'un segment initial de longueur constante de l'entrée, car des parties plus éloignées de l'entrée ne peuvent même pas être atteintes en temps constant.

D'un autre côté, si nous adoptons le modèle RAM à coût unitaire un peu plus puissant (et plus réaliste), dans lequel les opérations élémentaires sur les nombres bits sont comptées comme des étapes uniques, alors nous pourrons peut-être résoudre des problèmes non triviaux tâches, même en temps constant. Voici un exemple: $O(\log n)$

Instance: entiers , chacun donné au format binaire par bits. $n, k, l, d$ $O(\log n)$

Question: Existe-t-il un graphe à sommets, tel que sa connectivité au sommet est , sa connectivité aux bords est et son degré minimum est ? $n$ $k$ $l$ $d$

Notez que d'après la définition, il n'est même pas évident que le problème est en NP . La raison en est que le témoin naturel (le graphe) peut avoir besoin d' une description longue de bits, tandis que l'entrée n'est donnée que par bits. D'un autre côté, le théorème suivant (voir la théorie des graphes extrêmes de B. Bollobas) vient à la rescousse. $\Omega(n^2)$ $O(\log n)$

Théorème: Soit entiers. Il existe un graphe à sommets avec connectivité au sommet , connectivité aux bords et degré minimum , si et seulement si l'une des conditions suivantes est remplie: $n, k, l, d$ $n$ $k$ $l$ $d$

, $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$
$1\leq 2d+2-n\leq k\leq l = d< n-1$
$k=l=d=n-1.$

Comme ces conditions peuvent être vérifiées en temps constant (dans le modèle RAM à coût unitaire), le théorème conduit à un algorithme à temps constant dans ce modèle.

Question: Quels sont quelques autres exemples non triviaux d'algorithmes à temps constant?

cc.complexity-theory ds.algorithms time-complexity Andras Farago
la source

La vérification d'une preuve probabiliste vérifiable compte-t-elle?

David Eppstein du

Ne pensez pas que votre exemple est le temps

. Votre entrée a une longueur

, auquel cas le mot typique RAM n'autoriserait que les opérations

bits en une seule étape. (L'alternative est d'autoriser la taille des mots proportionnelle à la longueur d'entrée, mais dans ce cas, on peut nommer de nombreux algorithmes "à temps constant" ...) Vous pouvez essayer d'ajouter une chaîne de longueur

après ces nombres, mais alors je ne vois pas comment la vérification de ce format fonctionnerait dans

O (1)

$O(1)$

m = O (\log n)

$m=O(\log n)$

O (\log m)

$O(\log m)$

\geq n

$\geq n$

O (1)

$O(1)$ time: il semble que vous devez vérifier (via la recherche binaire, disons) que la longueur totale de la chaîne est bien

, ce qui nécessite

time.

Ω (\log n)

$\Omega(\log n)$

\log n

$\log n$

Ryan Williams

Je pense que la suggestion de David Eppstein pointe vers une direction plus intéressante: considérer les algorithmes aléatoires à temps O (1). Au moins dans ce cas, vous pouvez espérer que chaque bit d'entrée est accessible dans au moins une exécution possible de l'algorithme.

Ryan Williams

Un exemple simple d'algorithmes de temps O (1) randomisés est la médiane approximative (approximative dans le sens où elle divisera l'entrée environ 50-50). Choisissez simplement 1000000 éléments de l'entrée uniformément au hasard, calculez leur médiane et sortez-les.

Jukka Suomela

J'aime votre question mais l'inconvénient de votre exemple est qu'il repose sur un théorème mathématique. En poussant cela à la limite, vous pourriez dire: Instance Entiers positifs

. Question Y a-t-il un entier

tel que

(la réponse est Vrai ou Faux). Eh bien, il y a bien un algorithme à temps constant car la réponse est toujours False, mais ce n'est clairement pas le genre d'exemples que vous souhaitez.

x, y, z

$x, y, z$

n > 2

$n > 2$

x^{n} + y^{n} = z^{n}

$x^n + y^n = z^n$

J.-E.

Réponses:

L'article Algorithmes d'approximation à temps constant via les améliorations locales de Nguyen et Onak donne de nombreux exemples de schémas d'approximation à temps constant aléatoires: Correspondance maximale (le temps d'exécution ne dépend que du degré maximum du graphique), Définir la couverture, etc. Les auteurs présenter une méthode pour concevoir de tels algorithmes.

Lamine
la source

Il existe de nombreux exemples de jeux étudiés dans la théorie des jeux combinatoires où l'état d'un jeu peut être décrit par un nombre constant de valeurs entières. Pour certains d'entre eux, une stratégie gagnante pour le jeu peut être calculée en temps constant. Mais ils soulèvent également des questions sur ce qu'est exactement votre modèle de calcul.

L'un des jeux combinatoires les plus simples et les plus basiques est nim: l'un a un nombre constant de piles de haricots, et en un seul mouvement, vous pouvez supprimer n'importe quel nombre de haricots d'une pile, gagnant ou perdant (selon votre choix de règles) si vous prenez le dernier haricot. La stratégie optimale peut être calculée en temps constant si vous autorisez les opérations xor booléennes au niveau du bit (c'est-à-dire l'opérateur ^ dans les langages de programmation comme C / C ++ / Java / etc.) Est-ce un algorithme à temps constant dans votre modèle?

En voici un où l'on sait qu'il existe un algorithme déterministe exact à temps constant (dans un modèle étendu de calcul éventuellement irréaliste qui vous permet de tester la primalité d'un nombre en temps constant) mais on ne sait pas ce qu'est cet algorithme: étant donné un départ déplacer dans le jeu de monnaies Sylver , déterminer s'il s'agit d'un coup gagnant ou perdant. Un organigramme de ce problème est donné dans Berlecamp, Conway et Guy, Winning Ways , mais cela dépend d'un ensemble fini de contre-exemples pour une caractérisation générale des mouvements gagnants, et on ne sait pas ce que cet ensemble est (ou même s'il est vide).

Un autre exemple intéressant de la théorie des jeux combinatoires est le jeu de Wythoff. Chaque position de jeu peut être décrite par une paire d'entiers (c'est-à-dire un espace constant, dans votre modèle de calcul), les mouvements dans le jeu impliquent de réduire l'un de ces deux entiers à une valeur plus petite, et la stratégie gagnante implique de passer à une position où le rapport entre ces deux nombres entiers est aussi proche du nombre d'or que possible. Mais dans de nombreuses positions de jeu, il y a un choix: vous pouvez réduire le plus grand des deux entiers au point où il est (presque) le plus petit entier multiplié par le nombre d'or, ou le plus petit entier divisé par le nombre d'or. Un seul de ces deux choix sera gagnant. Ainsi, la stratégie optimale peut être définie en termes d'un nombre constant d'opérations arithmétiques, mais ces opérations impliquent un nombre irrationnel, le nombre d'or. Est-ce un algorithme à temps constant dans votre modèle? Peut-être ça' $n$ $\log n$

David Eppstein
la source

Merci, ce sont tous des exemples intéressants. Ils ont également joliment mis en lumière le fait que le concept de "temps constant" est moins clair que je ne le pensais à l'origine ...

Andras Farago

$|G|$ $G$ $p$ $m$ $m$ $|G|$ $G$ $p$ $m$ $G$ , alors le temps sera au moins $|G|$ . Si $m$ est fixe que temps constant, à savoir le temps $m$ , ce qui est constant car $m$ c'est réglé. D'un autre côté, si l'on est pédant, on peut affirmer qu'aucun algorithme à temps constant n'existe si l'algorithme doit d'abord lire une entrée de longueur variable pour prendre une décision.

orgesleka
la source