5
$\begingroup$

I would be interested in some References (books or articles) concerning an answer to the following question :

what is more difficult to calculate from the viewpoint of a computer : the "sum" or the "maximum" of a finite set of numbers ?

My guess is that "sum" and "maximum" are of the same level of difficulty, but I would like very much to know References concerning this question.

Thank you in advance.

George

$\endgroup$
4
  • 3
    $\begingroup$ Not a research-level theoretical computer science question. $\endgroup$ Dec 3 '10 at 11:40
  • 4
    $\begingroup$ @Dave: But I guess it could be turned into a research-level question. Can we come up with a model that separates sum and max? For example, could we show that in certain models, computing the sum of $n$ $b$-bit numbers requires strictly more extra space (in addition to the read-only input tape and write-only output tape) than max? Or is the answer always trivial? $\endgroup$ Dec 3 '10 at 12:09
  • $\begingroup$ What is the measure of difficulty your are interested in? What is the model of computation? $\endgroup$
    – Kaveh
    Dec 3 '10 at 14:03
  • 1
    $\begingroup$ I like the answers more than the question ! I wish we could change the question to the one Jukka proposes and use Kaveh's answer ;) $\endgroup$ Dec 3 '10 at 17:14
12
$\begingroup$

The sum of finitely many binary numbers can be computed in $TC^0$ and is in fact complete for $TC^0$ under $AC^0$ reductions.

The maximum of finitely many binary numbers can be computed in $AC^0$.

So from the circuit-complexity perspective, sum is more difficult.

$\endgroup$
2
  • $\begingroup$ Really? Could you please tell us how to compute the maximum of $n$ $n$-bit numbers in AC$^0$? $\endgroup$
    – slimton
    Dec 3 '10 at 16:04
  • 7
    $\begingroup$ @slimton: Note first that we can compare two numbers in $AC^0$. Then here is how to compute the maximum of $n$ numbers $x_1,\dots,x_n$, each of $n$ bits. First we compare all pairs of numbers. Next we compute for each $x_i$ the AND of all tests $x_i \geq x_j$. For each bit of $x_i$ we take the AND with this and the bit. Now, all numbers that are not equal to the maximum has been zeroed out. Now take the bitwise OR of all these numbers. $\endgroup$ Dec 3 '10 at 16:36
1
$\begingroup$

From pure algorithmic PoV in both cases there are N-1 addition operations.

For a computer though MAX might be harder to perform as there is one additional branch - determining the index of the currently max number. In sum operation this is not needed as interim result is just reused on the next number.

$\endgroup$
3
  • $\begingroup$ I do not have to add even once for finding the maximum. $\endgroup$
    – Raphael
    Dec 3 '10 at 12:57
  • $\begingroup$ Any comparison operation in effect does a subtraction and checks for 0 result. Subtraction is addition with different sign. Modern processors might do it differently but it all boils down to checking bits one against another and then branching based on the result (which i what I meant). Perhaps tried to say it in too few words. $\endgroup$ Dec 3 '10 at 14:25
  • $\begingroup$ The fact stands that for comparison I only have to check from the MSB downward to the first difference while for addition I have to look at all bits. This makes a difference. Comparing by subtracting is not a good implementation (in terms of TM). $\endgroup$
    – Raphael
    Dec 5 '10 at 13:25
1
$\begingroup$

What machine model do you want to use?

On RM, both are equally hard if you assume that $+$ and $<=$ are equally expensive (common assumption).

On 1-TM, sum is slightly more expensive since we have to add all bits compared to comparing only the the most signifikant bits (up to the first difference).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy