= 27d567bc2d48d9f40e9ccc20ea370b15)
cousin_it comments on What would you do with a solution to 3-SAT? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (78)
Solomonoff induction is uncomputable. It's closer to solving the halting problem than to solving NP-hard problems. An NP solver would be computable, just faster than today's known algorithms for SAT.
I know that. I was saying, given that people still prove things about Solomonoff induction's accuracy even though it's uncomputable, are there any results on how successful this type of prediction could be, relative to the standard set by Solomonoff induction? That is, how powerful can induction be if you have a mere NP oracle, compared to a halting oracle?