# When is an algorithm "equal" to another?

I have two algorithms $$P, Q$$ for solving the same problem (a decision problem on sequences in $$R^n$$) and I want to decide if they differ in any meaningful way. The following describes the constraints:

• $$P,Q$$ always halt on a defined, finite set of inputs $$S \subset R^n$$ and provide the same output (they compute the same function).
• For all inputs $$s \in S$$, both $$P,Q$$ perform the same operations.
• For all inputs $$s \in S$$, both $$P,Q$$ perform the same number of operations.
• For all inputs $$s \in S$$, both $$P,Q$$ use the same amount of memory.

For me (someone who doesn't have a background in algorithms), this seems like a reasonable notion of equality between $$P,Q$$ over $$S$$. Are there cases of two algorithms that satisfy these constraints yet differ in some meaningful way?

• Related question: cs.stackexchange.com/questions/31932/… Commented Aug 29 at 23:32
• @Pseudonym why do you believe this to be relevant? I assume for the purpose of showing how varied an algorithm's operations can be, but I am interested in defining a set of metrics that have reasonable exceptions for non-pathological cases Commented Aug 30 at 15:57
• It's related, but it's not the same question. Some of the answers delve into the question of whether or not two algorithms are "the same", or do "essentially the same thing". Commented Aug 30 at 23:20

This question is outside the realm of "ordinary" algorithm analysis and complexity theory. Of course this doesn't mean that questions like yours can't be interesting and people might study them. However, I don't think your criteria are great at distinguishing between algorithms. Most models of computation have a relatively small set of instructions, and complex algorithms likely utilize all of them, so your first criteria contains very little information. Another issue is that your criteria can be fooled by simple tricks. For example say $$P$$ and $$Q$$ are algorithms, $$P$$ performs fewer operations than $$Q$$, and they both use the same amount of memory. Suppose we make $$P'$$ an algorithm that performs $$P$$ and then does a number of useless operations so that it performs the same total number of operations as $$Q$$. Your criteria state that $$P'$$ and $$Q$$ equivalent.