I have been wondering about comparison versus RAM models and have some very basic sounding questions.

Is there a name for the subset of P (or FP really) that is computable by comparison RAM algorithms? For the avoidance of confusion we can think of the comparison RAM model as just being the normal RAM model where the input symbols are given in terms of rows/columns of a ternary matrix that tells us if pairs of symbols are bigger, the same, or smaller. That is we never get to find out or use the value of the input symbols.

What are the biggest known gaps for the time complexity of RAM and comparison RAM algorithms for natural problems coming from this subset of P (or FP)? We can imagine unnatural examples where comparisons are constant time but the RAM model has to spend a lot of time inputting the bits. Those are not the ones I am interested in. Sorting is the simplest example with a log gap for poly size inputs but is there anything bigger?

Related to the last question, is there some reason to suppose a maximum gap between (natural) RAM and comparison RAM problems? I suppose one route would be to say that you could simulate one with the other efficiently.


1 Answer 1


You can defiintely cook up promise problems where RAM is much stronger. Of course it's weird because you have to actually phrase your problems in terms of comparisons. suppose your memory is initialised into a permtuation, i.e. with memory registers x(1), ..., x(n) taking on the values 1, .., n exactly once each. The problem is to compute the # of i s.t. x(i) < x(1).

  • $\begingroup$ That is nice. The query doesn't actually tell you anything about the input other than queried item itself which is curious. $\endgroup$
    – Simd
    Commented Jul 5, 2012 at 18:24

Your Answer

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

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