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

I'm not saying that this type of proof was applied perfectly here, however, the notion of proving that solving problem X must be hard because solving it would solve problem Y, which is (at least for now) known to be hard is a fundamental methodology in the field of computational complexity theory. There is a strong academic basis in these types of lines of reasoning, specifically in computing and optimization.


I'm not a trained computer scientist but didn't Daniel Lemire (purportedly) answer a different question from what OP asked? In OPs question k is fixed, wouldn't that open up avenues to implementation different from when k is not?




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

Search: