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.
[ Parent
| on HN ]
There are no comments on this comment yet.