30 000 $ pour résoudre les problèmes de la règle 30 pour les automates cellulaires - un concours de Stephen Wolfram

Traduction originale dans mon blog


Site Web du concours

Expliquons aux lecteurs ce que signifie «Règle 30» - il s'agit d'un automate cellulaire élémentaire (voir Wiki ), dont l'état (la règle pour construire un nouveau niveau de cellules basé sur l'ancien) dans le système de nombres binaires est défini comme 0-0-0-1-1-1-1 -1-0, qui peut être interprété comme 30 en notation décimale.

Alors, où tout a-t-il commencé? - «Règle 30»

Comment se fait-il qu'une chose incroyablement simple produise quelque chose d'incroyablement complexe ? Cela fait près de 40 ans que je me suis familiarisé avec la Règle 30, mais cela m'étonne encore et me ravit. Pendant longtemps, c'est devenu ma découverte préférée dans l' histoire de la science, au fil des ans, cela a changé ma vision du monde et m'a conduit à une variété de nouveaux types de compréhension de la science, de la technologie, de la philosophie et bien plus encore .

Mais même après tant d'années, il y a encore de nombreux concepts de base sur la règle 30 qui nous restent inaccessibles. J'ai donc décidé qu'il était temps de tout faire pour stimuler le processus d'identification de l'ensemble de base de ces modèles de base.

Donc, aujourd'hui, j'offre aux candidats 30 000 $ comme prix total pour répondre aux trois questions principales concernant la règle 30.

La règle 30 est extrêmement simple:

Il existe une séquence de rangées de cellules noires et blanches (cellules) et, en tenant compte d'une rangée spécifique de cellules noires et blanches, les couleurs des cellules de la rangée ci-dessous sont déterminées, en considérant chaque cellule individuellement et ses cellules adjacentes adjacentes, puis la règle de substitution simple suivante leur est appliquée, à savoir:

Code

RulePlot[CellularAutomaton[30]]

[Regardez la vidéo qui, en quelques minutes, raconte l'essence des automates cellulaires et la règle 30 - note du traducteur]

Que se passe-t-il si vous commencez avec une seule cellule noire? [Une ligne de cellules blanches est prise, infinie des deux côtés et une cellule noire, puis les règles ci-dessus s'appliquent à cette ligne, une nouvelle ligne est obtenue, etc. - Note du traducteur ] Supposons (comme je l'ai fait moi-même au début) que la règle est assez simple, et le modèle obtenu sur la base de son travail devrait également être simple. Cependant, si vous menez une expérience, vous verrez ce qui se passe après les 50 premières étapes de l'algorithme:


Naturellement, nous pouvons supposer qu'à la suite de l'algorithme, un objet mathématique beaucoup plus simple sera obtenu. Cependant, voici ce qui se passe après les 300 premières étapes:



Cela montre qu'il existe un certain modèle - sur le côté gauche de la pyramide . Mais en même temps, de nombreux aspects de ce modèle ressemblent à quelque chose de aléatoire .

Il est incompréhensible qu'une règle aussi simple puisse finalement conduire à un comportement système aussi complexe. Sur cette base, je suis parvenu à la conclusion que dans l'univers informatique de tous les programmes informatiques possibles, ce comportement est assez courant, d'autant plus qu'il se retrouve presque partout.

Sur la base de cette hypothèse, j'ai développé une approche de la formation d'un tout nouveau type de science - basée sur les principes d' observation du fonctionnement d'algorithmes simples.

Progressivement, de plus en plus de preuves s'accumulaient sur ces principes.

Revenons cependant à la règle 30 et examinons en détail ce qu'elle nous permet exactement de faire et quelle est son utilisation? Que dire exactement du comportement de cet algorithme? Il est immédiatement évident que même les réponses aux questions les plus évidentes s'avèrent difficiles.

Même après des décennies pour lesquelles aucune réponse n'a été trouvée, j'ai décidé qu'il était temps de poser des questions spécifiques sur la règle 30, tout en stimulant ce domaine avec de sérieux prix en espèces.

J'ai déjà essayé de faire quelque chose de similaire en 2007, en fixant un prix pour avoir répondu à la question de base sur une machine Turing spécifique. Et dans ce cas, le résultat a été positif et n'a pas tardé à attendre. Quelques mois plus tard, ce prix a été remporté - après avoir établi pour toujours ce qu'est la plus simple des machines Turing universelles possibles, et aussi prouver de manière très convaincante le principe général d'équivalence informatique , que j'ai personnellement développé plus tôt.

Le concours de la règle 30 se fixe une fois de plus l'objectif de résoudre une tâche clé, à savoir: quelle est la complexité du comportement de la règle 30 ? Chacune des tâches pose une question dans ce domaine à sa manière et en particulier. Comme la règle 30 elle-même, ils sont tous d'une simplicité trompeuse dans leur cadre d'origine. Néanmoins, la solution à l'un d'entre eux sera une énorme réussite, qui contribuera finalement à éclairer les principes fondamentaux des propriétés de la formation de l'univers informatique, qui vont bien au-delà des spécificités de la règle 30.

Je travaille sur chacune de ces questions depuis plus de 35 ans . Et pendant tout ce temps, j'ai essayé de trouver la bonne idée dans le cadre d'une pensée mathématique ou informatique cohérente, dans le but de résoudre enfin au moins un de ces problèmes. Maintenant, je veux ouvrir ce processus à toute la communauté mondiale. Cependant, je serai intéressé de savoir ce qui peut être réalisé pour résoudre ces problèmes et quelles méthodes peuvent être utilisées dans ce cas.

Règle 30 - Tâches à résoudre

Quant aux tâches compétitives selon la Règle 30, je donne la priorité à l'une des caractéristiques clés de l'algorithme de la Règle 30, à savoir: le caractère aléatoire évident de la formation des cellules de sa colonne centrale . Commencez avec une cellule noire, puis regardez la séquence des valeurs de couleur des cellules dans cette colonne et vous arriverez à la conclusion qu'elles sont aléatoires:




Mais dans quel sens sont-ils "vraiment aléatoires" ? Et cette hypothèse peut-elle être prouvée? Chacune des tâches définies dans le cadre du concours utilise son propre critère de hasard, puis demande si la séquence est aléatoire selon ce critère.

Tâche 1: la colonne centrale reste-t-elle toujours non périodique?

Considérez le début de la colonne centrale de la règle 30:




Il n'est pas difficile de trouver que les valeurs de cette colonne ne sont pas répétées - ce n'est pas périodique. Mais le défi est, la colonne centrale deviendra-t-elle jamais périodique du tout? En lançant la règle 30, nous voyons que la séquence ne devient pas périodique, même au premier milliard d'étapes . Ce qui doit être fait pour établir et prouver cela avec certitude.

Voici le lien où se trouvent le premier million et le premier milliard de valeurs de cette séquence ( entrepôt de données Wolfram ).

Tâche 2: Chaque couleur de la cellule (noir ou blanc) est-elle en moyenne également probable dans la colonne centrale?

C'est ce que nous obtenons lorsque nous comptons le nombre de cellules noires et blanches séquentiellement à plusieurs étapes dans la colonne centrale de l'algorithme de la règle 30:




Les résultats sont certainement proches de l'égalité pour les cellules noires et blanches. Ici, la problématique (question du problème) est de savoir si cette relation converge vers 1 avec un nombre croissant d'étapes dans le cycle .

Tâche 3: Le calcul de la nième cellule de la colonne centrale nécessite-t-il au moins O ( n ) opérations?

Pour trouver la nième cellule dans la colonne centrale, vous pouvez toujours simplement exécuter la règle 30 pour n étapes, en calculant les valeurs de toutes les cellules à l'intérieur du diamant sélectionné dans la figure ci-dessous:




Mais si vous le faites directement, cela n ² mises à jour de cellules distinctes, par conséquent, la puissance de calcul requise augmente à mesure que O ( n ² ). La question de ce problème est de savoir s'il existe une méthode plus (ou la plus) rapide pour calculer la valeur de la nième cellule sans tous les calculs intermédiaires - ou, en particulier, en moins de O ( n ) opérations .

Les chiffres qui composent Pi

La règle 30 est un produit de l'univers informatique: un système basé sur l'étude de programmes simples possibles avec une nouvelle structure intellectuelle, fournie par le paradigme de l'informatique. Cependant , les tâches que j'ai définies dans le concours pour la règle 30 ont des analogues en mathématiques, qui existent depuis des siècles .

Considérez les valeurs des nombres dans le nombre Pi . Le comportement de ces nombres est similaire à la génération de données dans la colonne centrale de l'algorithme de la règle 30. Autrement dit, il existe un algorithme donné pour les calculer, et une fois formulés, ils semblent presque aléatoires pour toutes les tâches.




Juste pour rendre l'analogue un peu plus proche, voici les premiers chiffres de Pi dans le système numérique avec base 2:




Et voici les premiers bits de la colonne centrale de la règle 30:




Pour le plaisir, vous pouvez les convertir en décimal:




Bien sûr, les algorithmes bien connus pour calculer les chiffres de Pi sont beaucoup plus compliqués que la règle relativement simple de génération de cellules dans la colonne centrale de la règle 30. Alors, que savons-nous des chiffres de Pi?

Tout d'abord, nous savons qu'ils ne se répètent pas. Cela a été prouvé dans les années 60 du 18e siècle, quand il a été démontré que Pi est un nombre irrationnel , car les seuls nombres dans lesquels les nombres sont répétés sont des nombres rationnels. (En 1882, il a également été démontré que Pi est transcendantal , c'est-à-dire qu'il ne peut pas être exprimé à travers les racines des polynômes).

Quel genre d'analogie peut-on tirer de la formulation du problème 2? Savons-nous que dans une séquence de chiffres de Pi, différents chiffres se produisent avec la même fréquence? À ce jour , plus de 100 trillions de chiffres binaires ont été calculés - et les fréquences des chiffres mesurés sont très proches (dans les 40 premiers trillions de chiffres binaires de Pi, le rapport des unités aux zéros est d'environ 0,99999998064). Mais lors du calcul de la limite, les fréquences seront-elles exactement les mêmes? Les scientifiques posent cette question depuis plusieurs siècles, mais jusqu'à présent, les mathématiques n'ont pas pu y répondre.

Pour les nombres rationnels, les séquences de chiffres qui les composent sont périodiques, et il est facile de déterminer les fréquences relatives d'occurrence de ces nombres dans un nombre. Cependant, pour la séquence de chiffres de tous les autres nombres «créés par la nature (naturellement construits)», dans la plupart des cas, on ne sait pratiquement rien de ce que les fréquences des chiffres inclus dans le nombre ont tendance. Il serait logique de supposer qu'en fait, les chiffres de Pi (ainsi que la colonne centrale de la règle 30) sont « normaux » dans le sens où non seulement chaque chiffre individuel, mais aussi tout bloc de chiffres d'une longueur donnée se rencontrent avec une fréquence maximale égale. Et, comme cela a été noté dans les travaux sur ce sujet des années 30, il est tout à fait possible de "construire une construction numérique (modèle)" de nombres normaux. La constante de Champernone obtenue en combinant les chiffres d'entiers consécutifs est un exemple du raisonnement ci-dessus (le même peut être obtenu sur la base de n'importe quel nombre normal en combinant les valeurs des fonctions d'entiers consécutifs):




Il convient de noter que le point ici est que pour les nombres «naturellement construits» formés par des combinaisons de fonctions mathématiques standard, aucun exemple découvert n'est trouvé où une séquence régulière de nombres serait trouvée. Naturellement, en fin de compte, cette disposition dépend de ce que l'on entend par «régularité» et, à un certain stade, la tâche se transforme en une sorte de recherche numérique-analogique pour l'intelligence extraterrestre . Cependant, rien ne prouve qu'il ne soit pas possible, par exemple, de trouver une combinaison complexe de racines carrées qui aurait une séquence de nombres avec une régularité très évidente.

Alors, enfin, considérez l'analogue du problème 3 pour Pi? Contrairement à la règle 30, où la façon évidente de calculer les éléments dans une séquence est une étape à la fois, les méthodes traditionnelles de calcul des chiffres de Pi incluent l'obtention des meilleures approximations de Pi en tant que nombre exact. Avec la série standard ("bizarre") inventée par Ramanujan en 1910 et améliorée par les frères Chudnovsky en 1989, les premiers membres de cette série donnent les approximations suivantes:




Alors, combien d'opérations sont nécessaires pour trouver le nième chiffre? Le nombre de termes requis dans la ligne est O ( n ). Mais chaque condition doit être calculée avec une précision à n chiffres, ce qui nécessite au moins O ( n ) opérations de calcul distinctes, ce qui implique qu'en général les charges de travail de calcul seront supérieures à O ( n ).

Jusqu'aux années 1990, on supposait qu'il n'y avait aucun moyen de calculer le nième chiffre de Pi sans calculer tous les précédents. Mais en 1995, Simon Pluff a découvert qu'il est effectivement possible de calculer, bien qu'avec une certaine probabilité, le nième chiffre sans calculer les précédents. Et bien que l'on puisse penser que cela vous permettrait d'obtenir le nième chiffre en moins de O ( n ) opérations, le fait que vous ayez besoin d'effectuer des calculs avec une précision de n chiffres signifie qu'au moins O ( n ) opérations.

Résultats, analogies et intuition

Tâche 1: la colonne centrale reste-t-elle toujours non périodique?

Des trois prix du concours Rule 30, c'est celui dans lequel la plupart des progrès dans la résolution de ce problème ont déjà été réalisés. Comme on ne sait toujours pas si la colonne centrale de la Règle 30 deviendra périodique, Erica Jen en 1986 a montré que deux colonnes ne peuvent pas être périodiques. Et en fait, c'est le cas, et on peut également plaider en faveur du fait qu'une colonne en combinaison avec des cellules individuelles dans une autre colonne ne peut pas être périodique .

La preuve de la paire de colonnes utilise une caractéristique de la règle 30. Considérez la structure de la règle:




Il est possible de dire simplement que pour chaque triple de cellules, la règle détermine la couleur de la cellule centrale, mais pour la règle 30, vous pouvez également exécuter efficacement la règle sur le côté: en tenant compte de la cellule à droite et au-dessus, vous pouvez également déterminer de manière unique la couleur de la cellule à gauche. Cela signifie que si vous prenez deux colonnes adjacentes, vous pouvez restaurer l'intégralité du modèle sur la gauche :




Cependant, si les colonnes avaient une structure périodique, il s'ensuivrait immédiatement que le modèle restauré devrait également être périodique. Ainsi, par exemple, par construction, au moins les conditions initiales ne sont certainement pas périodiques, et donc les deux colonnes ne peuvent pas être périodiques. La même affirmation est vraie si les colonnes ne sont pas adjacentes et si toutes les cellules des deux colonnes ne sont pas connues. Cependant, il n'existe aucun moyen connu de distribuer cette disposition pour une seule colonne, telle qu'une colonne centrale, et cela ne résout donc pas la première tâche du concours en vertu de la règle 30.

Alors, que peut-on utiliser pour le résoudre? S'il s'avère que la colonne centrale est finalement périodique, vous pouvez simplement la calculer. Nous savons que ce n'est pas périodique pour le premier milliard d'étapes, mais nous pouvons au moins supposer qu'il peut y avoir un processus de transition avec des milliards d'étapes, après quoi il devient périodique.

Pensez-vous que cela soit crédible? Des transitoires se produisent - et théoriquement (comme dans le problème classique de l'arrêt d'une machine de Turing ), ils peuvent même être de longueur arbitraire. Ici, nous regardons un exemple - trouvé lors de la recherche - Règles avec 4 couleurs possibles (code commun 150898). Supposons que nous exécutions 200 étapes et, comme vous pouvez le voir, la colonne centrale sera complètement aléatoire:




Après 500 étapes, le modèle entier semble complètement aléatoire:




Ici, vous pouvez voir qu'à l'approche de la colonne centrale, quelque chose de surprenant se produit: après 251 étapes, la colonne centrale semble renaître à une valeur fixe (ou au moins fixée à plus d'un million de pas):




La même transition pourrait-elle se produire dans la règle 30? Examinez les motifs de la règle 30 et sélectionnez ceux où les diagonales de gauche ont une périodicité:




Apparemment, il y a une bordure qui sépare l'ordre à gauche du trouble à droite. Et, au moins pour les 100 000 premiers pas environ, il semble que la frontière se déplace en moyenne d'environ 0,252 pas vers la gauche à chaque pas - avec quelques écarts aléatoires :




Mais comment découvre-t-on finalement à quel point ces fluctuations cesseront d'être significatives, à tel point qu'elles obligent l'ordre de gauche à traverser la colonne centrale et, peut-être, à rendre périodique l'ensemble du modèle? À en juger par les données disponibles, l'hypothèse semble peu probable, alors que je ne peux pas dire exactement comment cela peut être déterminé.

C'est bien sûr précisément le cas qui illustre l'existence de systèmes avec des «transitoires» exceptionnellement longs. Considérons maintenant la distribution des nombres premiers et calculons LogIntegral [ n ] - PrimePi [ n ]




Oui, il y a des fluctuations, mais dans cette illustration, il semble que cette différence sera toujours dans la zone positive. Et c'est, par exemple, ce dont parlait Ramanujan, mais finalement il s'avère que ce n'est pas le cas . Au début, la limite de l'endroit où il a échoué était, à cette époque, astronomiquement grande ( Skives numéro 10 ^{10 10 964} ). Et bien que personne n'ait encore trouvé de valeur explicite de n pour laquelle la différence soit négative, on sait que jusqu'à n = 10 ³¹⁷ elle doit exister (et finalement la différence sera négative).

Je suis d'avis que rien de ce genre n'arrive à la colonne centrale de l'article 30, mais jusqu'à présent, nous n'avons aucune preuve que cela est impossible, cela ne peut être soutenu.

Il convient de noter qu'il est possible de faire l'hypothèse que bien qu'il soit fondamentalement possible de prouver la périodicité en révélant la régularité dans la colonne centrale de la règle 30, rien de ce genre ne peut être fait pour la non-périodicité. Il est connu qu'il existe des motifs dont les colonnes centrales sont non périodiques, bien qu'elles soient très régulières. La classe principale de ces exemples sont les modèles imbriqués. Voici, par exemple, une illustration très simple de la règle 161, dans laquelle la colonne centrale a des globules blancs lorsque n = 2 ^k :




Et voici un exemple légèrement plus complexe (de la règle bicolore 69540422 pour deux voisins) , dans lequel la colonne centrale est une séquence Thue - Morse - ThueMorse [ n ]:




On peut supposer que la séquence Thue - Morse est générée par l'application séquentielle de la substitution:




Il s'avère que le nième terme de cette séquence est défini comme Mod [ DigitCount [ n , 2, 1], 2] - cet objet ne sera jamais périodique.

Se pourrait-il que la colonne centrale de la règle 30 puisse être générée par remplacement ? Si tel est le cas, je serais étonné de ce fait (bien qu'il semble y avoir des exemples naturels lorsque des systèmes de substitution très complexes apparaissent ), mais encore une fois, tant qu'il n'y a aucune preuve de cela.

Il convient de noter que toutes les tâches compétitives de la règle 30 sont prises en compte dans la formulation d'un algorithme qui s'exécute sur un nombre infini de cellules. , n , , ( )? , 2 ⁿ — , , . n =5:




n =5 n =11:




, , , , . , 2 ⁿ ( , , ).

, n 30 , , 2 ⁿ . , ( ):




, , n 2 ^{0.63 n} . , , . , , ? .

2: ?

10000 30:




:




:




, , 1 () 0 (), , , , , , , .

. 10 000 :




, 1? …

, :




, , . 1 , :




, ? . , . , , , , .

, , 30, .

, , k . , 2 ^k . , - , , , , 30 k ( ).

, . , , k =22, 2 ^k , , :




, , . , – , , .

— — , , , , , , 30, , , , , .

30 , , « », , , , , , . , «»: 30, , , , , , , , 30.

, . 30, , - , , , 30, , , - .

. 30 , , . , , 30 - ( ), , , , 30. 200 :




, :




, , , 0 1.

1900- . , , FractionalPart [ hn ] n h . , FractionalPart [ h ⁿ ] h ( ), — FractionalPart [(3/2) ⁿ ] — . (, , 16- , , 2- FractionalPart [16 x _{n -1} + r [ n ]], r [ n ] n .)

3: n- O( n ) ?

, 150 :




, ( ), , :




n- ? , , : Mod [ IntegerExponent [ n , 2], 2]. , n , , .

, « »? , n , Log [2, n ] . , , O(log n ) .

- 30? , n- , 30 n ² , , . , -, , , — , , , , , .

« » (, , . .), , , , , (, , 3D- . .), .

, 1980- , , , , , , , .

, 3 30 , , . ( O( n ) ; O( n ^α ) α <2, , , O(log ^β ( n )) — , , .)

3 , , n- , O( n ), 150 .

O ( n )? () , « »? , — — , , .

, . , , , n , , , n , (, «», O(log n ) .

, . , , , , Wolfram Language . « ». , , Wolfram Language , .

, 30 , 3 , , , , , , n- , O( n ) , .

, , . , , . , , , , , — , O(log n ) , n .

, P NP . , 30 ( P LOGTIME ), , , , . , , , n n , O( n ² ) , , P (« »), , , , , NP. («») , , , , 2 ⁿ .

, 2 ⁿ , , . , NP- , , , NP . 30 NP-? , , ( - , 30 NP).

30 . : 30 , , 30, «» , , , , .

, 256 110 ( , ), 110 , , , . , , , «» 110 .




30, , — , «» , . , , 30 , , , , .

, , , , , 30. , , (, ) , , . , , — , . , .

, , 3. , , , , n- ?

, 30 . , 2 ^{m 2} m × m , , . , , , O( n ² ) ( ). , O( n ) ? .

, 1 , , - O( n ) — , « ». , ( , 2 ), , , .

- , , , ? , , .

. «» , , , . 30 - . ( — — 30 Wolfram Language, « !» ).

: « - , , ». ? , , , - . . , — , . , , , — - «» 30.

, 30. , 30 - . , , , - 30 , , , , — 30, , , , .

. , 3 2 6 :




, 6 . ( 2 ). , , .

s- n . s- 3 ⁿ , «» ( b — , 2 6) Mod [ Quotient [3 ⁿ , b ^s ], b]. ? , 3 ⁿ n , : , , 3 ⁿ , log( n ). , , , . , 30, , - , .

3 n - 30 , , O( n ), , n , . , r [ n ] , r [ n ] «O-» n , , MaxLimit [ r [ n ]/ n , n →∞ ]<∞.

, ( - ), . , r [ n ] n , , , - , , r [ n ] . , - n ( - ), r [ n ] . , , , r [ n ] O( n ).

30

, ( , ).

Wolfram Language t 30 :




c [ t ].

1: ?

p i t , t > i , [ t + p ] c [ t ].

2: ?

c [ t ]/ t t →∞ 1/2.

3: n- O( n ) ?

machine[ m ] , m (, TuringMachine [...]), machine[ m ][ n ] { v , t }, v — , t — (, ). :




« m, , machine[ m ] n c [ n ] , n , ». ( m , «» ).

, , , , . 3 ( ), , 1 2, . 3 ( ), , 1 . : 1 , , 3 .

1 , , , , , 2. , 2 - 3. , , O( n ) — , , 3, , .

, , ?

1 , , , 30 - , . , 1 , . , , - , .

( , ), 2, 3 , — , , , . , 3 , , (, , ), O( n ) .

, - . , n n- . . , - , . , , n n . , . , « » . , n , . , , O( n ) .

: ? « », / ( ).

, , ( )? , , , , «» , -, ( ) , .

, , . , , , . , () .

, , , , : « ». , , , .

, — - . - n , . . — (« » . .). , , , .

— , , . , ( FindEquationalProof ). , () .

, , , — , . — , .

, . Wolfram|Alpha (, ) , . , .

, , - , , , , .

? , «» , . Wolfram Language , . Wolfram Language, .

« »? , , - . . - , , «» , , - ( ), . , , «» — , .

?

, ? . . , . - , . . - , , .

, , «» — , — , « ». , 2,3 2007 .

— , , 30, , . . - ( , , ). , , ( ) , , .

n — 30 n , n . Wolfram Language . , 0,4 100 000 :




, 30 Xor [ p , Or [ q , r ]], . , CellularAutomaton :




. . , , 30, , 30 , , , : .

. , , «» . 30 — . , , , .

— , , . , , 30, .

, , 30, . 45° , 30, , . ; . ?

? ? - ? , , , , , .

? 30, . , , , , , . , - , , , , , , - .

– , «» . ( , - ). , , , , « » :




, , , . ? , « » ?

, (, ), , - 30?

« 30». , «» ? 30 , ? «» ?

, , 30, , , , 30, . 256 ( ) , , :




, . , . , , . , , , « 30», .

« 30». 30 ( 1), , — , .

2, 30, , .

3 . n- O( n ^γ ) γ <2 ( - )? , n- , O(log( n )) ? O(log( n )) ? ? . ?

, 30. 30, (, , 110) , 30.

, NP-, 30 , , NP-? , . , , , « », 30?

?

2007 2,3 , — , , , . , . 30? . 40 , - ( , !). , , (, ) .

, - ( ), , , , , , , . ( ), , , .

, « » ( , ), . , . , (« » . .). . , - « », , , …

, . , , . , , . , .

, 30 40 , - .

Wolfram Language?
« Wolfram » ( ).