Random Access Machines mit nur Addition, Multiplikation, Gleichheit

In der Literatur ist ziemlich klar, dass kostenpflichtige RAMs mit primitiver Multiplikation insofern unvernünftig sind, als sie

können von Turing-Maschinen nicht in Polynomzeit simuliert werden
kann PSPACE-vollständige Probleme in der Polynomzeit lösen

Alle Referenzen, die ich zu diesem Thema finden kann (Simon 1974, Schonhage 1979), beziehen sich jedoch auch auf Boolesche Operationen, Ganzzahldivisionen usw.

Gibt es irgendwelche Ergebnisse für die "Angemessenheit" von RAMs, die nur Addition, Multiplikation und Gleichheit aufweisen? Mit anderen Worten, welche haben keine Booleschen Operationen, keine Ganzzahltrennung, keine Subtraktion usw?

Man würde denken, dass solche RAMs immer noch ziemlich "unvernünftig" sind. Die wichtigste rote Fahne ist, dass sie die Erzeugung von exponentiell großen ganzen Zahlen in linearer Zeit ermöglichen, und aufgrund der konvolutionären Effekte der Multiplikation kann dies besonders komplex werden. Ich kann jedoch keine Ergebnisse finden, die belegen, dass dies zu irgendwelchen "unvernünftigen" Ergebnissen führt (exponentielle Beschleunigung der Turing-Maschine, unvernünftige Beziehung zu PSPACE usw.).

Hat die Literatur Ergebnisse zu diesem Thema?

complexity-theory reference-request computation-models history Mike Battaglia
quelle

Yuval Filmus hat eine kurze Notiz, die zusammenfasst, wie man ein Problem in NP (und ich denke, ein Problem in PSPACE?) In polynomialer Zeit mit Stückkosten-RAMs löst. Vielleicht wird er einen Link dazu veröffentlichen, und Sie können die Methoden dort überprüfen, um festzustellen, ob sie verallgemeinert werden können, um die Notwendigkeit einer Teilung zu beseitigen.

\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)$ . This can be done in time polynomial in

n

$n$ and

c

$c$ if we allow division, but can it be done without division? If it can, I suspect similar results are going to apply to your model as well.

D.W.

Do you know where this note is? I've seen literature on unit-cost RAMs being unreasonably powerful when boolean operations are permitted, and truncated division (or shift), with the boolean operations and truncations basically turning the whole thing into a huge parallel device. But, there should be some result somewhere showing that even just unit-cost multiplication is "unreasonable" without the other things, because as mentioned, you can quickly compute numbers with more digits than is contained in the observable universe. But, I cannot find a proof of this.

Mike Battaglia

@D.W. My note shows how to solve all problems in PSPACE in polynomial time. Unfortunately, you need to use bitwise operators (bitwise AND and OR; the two are equivalent). At the time I briefly thought about the very question that you're asking, but came to no conclusion. You can find all of this here, though it seems you are already aware of it.

Yuval Filmus

Thanks - did indeed see it. I guess I'm wondering, how could it not be the case that there's no speedup with just multiplication? You can keep repeatedly squaring numbers to produce exponentially large, very complex patterns that seem crazy for a Turing machine to produce in polynomial time. Shouldn't there be some kind of growth argument that you can make, since it appears we are using exponential space in linear time (violating

P \in PSPACE

$\text{P} \in \text{PSPACE}$ )? These problems don't apply for unit-cost addition, just multiplication.

Mike Battaglia

Random Access Machines mit nur Addition, Multiplikation, Gleichheit

Antworten: