News for hackers. Stuff that matters.
Re:When are two proofs essentially the same? (2007) by Sharlin on Tuesday October 29, 2024 @03:21PM (#41988344)
From complexity analysis we can adopt the concept of polynomial-time reducibility and might define a type of equivalence relation where two algorithms are equivalent only if both are pt-reducible to each other. Intuitively it’s not a sufficient condition for "sameness" – otherwise, for example, all NP-complete problems are the "same" and solvable with the "same" algorithm – but it’s arguably a necessary one.

There are no comments on this comment yet.