Hacker News new | past | comments | ask | show | jobs | submit login

> So we’ve got an exact algorithm that needs to solve an np-complete problem to produce a result, making it at least as hard.

This is not correct. It's very obvious that all-pair similarity search can be solved in O(n^2) calls to the similarity metric, as stated in the readme. So unless the metric itself falls outside P, this problem is easy (but still hard to scale up in practice, of course)




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

Search: