2

I have written two widely different algorithms which are supposed to give same output for same input.But how do I prove they are equivalent? Is it even possible? I know that there is no general algorithm to prove equality of two algorithms. But is it possible if two algorithms are given? ' I would appreciate if you give links to some books or Pdf related to this even if you don't give the steps. Thanks in advance.

Indigo1729
  • 153
  • 8
  • 3
    Possible duplicate on Computer Science : https://cs.stackexchange.com/q/2059. It's impossible to say more unless we knew the two algorithms. – Michael Foukarakis May 15 '17 at 11:03
  • This question is better suited for the cs or cstheory sites. – H H May 15 '17 at 11:05
  • It may be easier to show, that each of these is solving your problem (without comparing those two). But Michael's link is great! My first sentence might be an equivalent to number 3 of those approaches mentioned in the linked-answer. – sascha May 15 '17 at 11:05
  • "there is no general algorithm to prove equality of two algorithms". Didn't you just answer your own question? – Bernhard Barker May 15 '17 at 12:26
  • This question is asking for books or documentation elsewhere. I doubt it will be well received on other sites either. – moooeeeep May 15 '17 at 12:29
  • @MichaelFoukarakis Thanks for the link. I wanted some guidance in this direction and not the answer itself.I am a noob in this area and also new to stack exchange. – Indigo1729 May 15 '17 at 17:19

2 Answers2

1

You might be interested in formal algorithms analysis. If you can prove that both of them produce the desired output, given an input, then they are equivalent from the input-output perspective.

Formal analysis (proving). The aim of the formal analysis is to prove that the algorithm works for any instance of data input. The main advantage of this approach is that if it is rigourously applied it guarantee the correctness of the algorithm. The main disadvantage is the difficulty of finding a proof, mainly for complex algorithms. In this case the algorithm is decomposed in subalgorithms and the analysis is focused on these (simpler) subalgorithms. On the other hand the formal approach could lead to a better understanding of the algorithms. This approach is called formal due to the use of formal rules of logic to show that an algorithm meets its specification.

danbanica
  • 3,018
  • 9
  • 22
  • This is what unit tests are doing, right? Try edge cases and random inputs and see if the output is correct. – maraca May 15 '17 at 12:09
  • 1
    @maraca That would be "experimental analysis", which is usually simpler to do, but you can usually not cover in that way all possible inputs. Yes, "formal analysis" has the same purpose (proving that the algorithm is correct), but using mathematical proofs. – danbanica May 15 '17 at 12:20
  • no, it is based on mathematical notions. it is even used for hard real time system. You can search for frama-C for exemple. – Matt May 15 '17 at 12:22
  • Thanks, I see. One problem with this approach is that you can prove that your program is correct (can you really? Halting problem) but you cannot prove that the algorithms are the same, e.g. bubble and merge sort are both stable sort algorithms but it is not the same algorithm. – maraca May 15 '17 at 12:29
  • @maraca my answer mentions that this is a way to prove the equivalence from the input-output perspective. Other aspects (_e.g._ complexities of the algorithms) are not taken into account, but as I understand the question, they are not supposed to be considered. – danbanica May 15 '17 at 13:01
  • @maraca Regarding the halting problem, I'm not sure I understand what you mean. There are for sure situations where you can formally prove that an algorithm is correct (i.e. it computes a given function). However, I agree that this easily becomes impractical, and that is a reason why unit testing is actually more popular. – danbanica May 15 '17 at 13:03
  • @qwertyman Thanks. I think that is exactly what I need. In my algorithms, I know two outputs will correspond to complementary inputs(n and k-n). Thus if I can prove outputs are equivalent, I will also prove that function(algorithm) is symmetric w.r.t 'k/2 or k/2+1/2'(I know this as fact just want prove). Thanks again!!! – Indigo1729 May 15 '17 at 17:30
0

Equality of algorithms is almost non sense. What you (probably) want is to prove that two algorithms compute/realize the same function. So you just have to prove that each algorithm realizes the function. Hoare logic may be your friend.

Jean-Baptiste Yunès
  • 34,548
  • 4
  • 48
  • 69
  • Thanks. I am new to this algorithm analysis, hence could not convey my question more clearly. But I wanted what you just said i.e same input gives same output or they realize the same function – Indigo1729 May 15 '17 at 17:34