News for hackers. Stuff that matters.

A comment on Decreasing the Number of Memory Accesses 1/2. Parent comment

Re:Decreasing the Number of Memory Accesses 1/2 by mort96 on Friday March 31, 2023 @04:38PM (#35393300)
I don't have any, I haven't thought about it enough. However, the reason I think it might be interesting is that checking if something is a correct solution is often easier than coming up with a correct solution for a lot of classes of problems (assuming P!=NP and all that).

And maybe you can't make a polynomial time verifier which works in the general case, but maybe you can make a useful one which handles a lot of cases.

[ Parent | on HN ]
Re:Decreasing the Number of Memory Accesses 1/2 by c-cube on Saturday April 01, 2023 @08:22AM (#35399670)
I'm pretty sure that program equivalence is undecidable, ie you literally can't write this validation pass at all. There's a C compiler (compcert) that is formally verified to preserve the semantic of its input C code down to assembly, but it takes a lot of human developed proofs in Coq to get there.
[ Parent | on HN ]