13
$\begingroup$

The literature is fairly clear that unit-cost RAMs with primitive multiplication are unreasonable, in that they

  1. cannot be simulated by Turing machines in polynomial time
  2. can solve PSPACE-complete problems in polynomial time

However, all of the references I can find on this topic (Simon 1974, Schonhage 1979) also involve boolean operations, integer division, etc.

Do there exist any results for the "reasonableness" of RAMs that only have addition, multiplication, and equality? In other words, which do not have boolean operations, truncated integer division, truncated subtraction, etc?

One would think that such RAMs are still quite "unreasonable." The main red flag is that they enable the generation of exponentially large integers in linear time, and due to the convolution-ish effects of multiplication, this can get particularly complex. However, I cannot actually find any results showing that this allows for any sort of "unreasonable" result (exponential speedup of Turing machine, unreasonable relationship to PSPACE, etc).

Does the literature have any results on this topic?

Improve this question
$\endgroup$
16
  • $\begingroup$ Yuval Filmus has a short note summarizing how to solve any problem in NP (and I think any problem in PSPACE?) in polynomial time, using unit-cost RAMs. Perhaps he'll post a link to that and you can review the methods there to see if they can be generalized to eliminate the need for division. $\endgroup$
    – D.W. ♦
    Jun 14, 2017 at 22:31
  • $\begingroup$ Can you think of a way to compute the number $\sum_{i=0}^{2^n-1} 2^{ci}$, where $c$ is a small constant, in your model, using time polynomial in $n,c$? In other words, we want to compute $(2^{c 2^n}-1)/(2^c-1)$. This can be done in time polynomial in $n$ and $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. $\endgroup$
    – D.W. ♦
    Jun 14, 2017 at 22:42
  • $\begingroup$ 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. $\endgroup$
    – Mike Battaglia
    Jun 15, 2017 at 19:13
  • 3
    $\begingroup$ @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. $\endgroup$
    – Yuval Filmus
    Jun 15, 2017 at 19:48
  • $\begingroup$ 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 $\text{P} \in \text{PSPACE}$)? These problems don't apply for unit-cost addition, just multiplication. $\endgroup$
    – Mike Battaglia
    Jun 20, 2017 at 20:06

1 Answer 1

Reset to default
2
$\begingroup$

The other day I was reading a paper on parallelized random access machines without bit operations, which sounded very much like what you are describing. For these models NC is known not to equal P. See here: https://epubs.siam.org/doi/10.1137/S0097539794282930

The paper can also be found on Professor Mulmuley’s website.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.