News for hackers. Stuff that matters.
Re:LLMs and Programming in the first days of 2024 by renonce on Monday January 08, 2024 @10:30AM (#38913350)
That's an underutilization of the complexity theory. Since not all problems are formulated as being Turing-complete, there are better theorems to apply than Rice's Theorem, such as:

* IP=PSPACE (you can verify correctness of any PSPACE computation in polynomial time)

* NIP=NEXPTIME (you can verify correctness of any NEXPTIME computation with two non-cooperative provers)

* NP=PCP(1,log(n)) (you can verify correctness of any NP statement with O(log(n)) bits of randomness by sampling just O(1) bits from a proof)

What these means is that a human is indeed able to verify correctness of the output of a machine with stronger computational abilities than the human itself.

There are no comments on this comment yet.