Comparison versus RAM models

Question

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.

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).