Machines à accès aléatoire avec seulement addition, multiplication, égalité

La littérature est assez claire sur le fait que les RAM à coût unitaire avec multiplication primitive sont déraisonnables, dans la mesure où elles

ne peut pas être simulé par les machines de Turing en temps polynomial
peut résoudre des problèmes PSPACE complets en temps polynomial

Cependant, toutes les références que je peux trouver sur ce sujet (Simon 1974, Schonhage 1979) impliquent également des opérations booléennes, une division entière, etc.

Existe-il des résultats pour le « caractère raisonnable » de RAMs qui n'ont plus, la multiplication et l' égalité? En d'autres termes, qui n'ont pas d'opérations booléennes, division entière tronquée, soustraction tronquée, etc.?

On pourrait penser que ces RAM sont encore "déraisonnables". Le principal drapeau rouge est qu'ils permettent la génération d'entiers exponentiellement grands en temps linéaire, et en raison des effets de convolution de la multiplication, cela peut devenir particulièrement complexe. Cependant, je ne peux pas réellement trouver de résultats montrant que cela permet tout type de résultat "déraisonnable" (accélération exponentielle de la machine Turing, relation déraisonnable avec PSPACE, etc.).

La littérature a-t-elle des résultats sur ce sujet?

complexity-theory reference-request computation-models history Mike Battaglia
la source

Yuval Filmus a une courte note résumant comment résoudre tout problème dans NP (et je pense que tout problème dans PSPACE?) En temps polynomial, en utilisant des RAM à coût unitaire. Peut-être qu'il publiera un lien vers cela et vous pouvez y revoir les méthodes pour voir si elles peuvent être généralisées pour éliminer le besoin de division.

Pouvez-vous trouver un moyen de calculer le nombre

, où

est une petite constante, dans votre modèle, en utilisant le polynôme temporel dans

? En d'autres termes, nous voulons calculer

. Cela peut être fait en polynôme temporel en

\sum_{i = 0}^{2^{n} - 1} 2^{c i}

$\sum_{i=0}^{2^n-1} 2^{ci}$

c

$c$

n, c

$n,c$

(2^{c 2^{n}} - 1) / (2^{c} - 1)

$(2^{c 2^n}-1)/(2^c-1)$

n

$n$

c

$c$ si nous permettons la division, mais cela peut-il se faire sans division? Si c'est le cas, je soupçonne que des résultats similaires s'appliqueront également à votre modèle.

Savez-vous où se trouve cette note? J'ai vu de la littérature sur les RAM à coût unitaire déraisonnablement puissantes lorsque les opérations booléennes sont autorisées, et la division (ou décalage) tronquée, les opérations booléennes et les troncatures transformant essentiellement le tout en un énorme dispositif parallèle. Mais, il devrait y avoir un résultat quelque part montrant que même une multiplication par coût unitaire est "déraisonnable" sans les autres choses, car comme mentionné, vous pouvez rapidement calculer des nombres avec plus de chiffres que ceux contenus dans l'univers observable. Mais, je ne trouve pas de preuve de cela.

Mike Battaglia

@DW Ma note montre comment résoudre tous les problèmes dans PSPACE en temps polynomial. Malheureusement, vous devez utiliser des opérateurs au niveau du bit (AND et OR au niveau du bit; les deux sont équivalents). À l'époque, j'ai brièvement réfléchi à la question que vous posez, mais je n'ai pas abouti. Vous pouvez trouver tout cela ici , bien qu'il semble que vous en soyez déjà conscient.

Yuval Filmus

P \in PSPACE

$\text{P} \in \text{PSPACE}$

Machines à accès aléatoire avec seulement addition, multiplication, égalité

Réponses: