Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: