Consider this problem: given positive integers a,b,c, are there positive integers x,y such that a*x*x+b*y=c? Amazingly, it is NP-complete. Can anyone explain to me how it manages to be complete?
This is an impressively simple NP-complete problem description.
One obvious point is that you can solve it in O(sqrt(c)lg k) time where k=max(a,b,c), just by trying all the values of x such that x^2<=c. But of course, in terms of the size of the inputs n, e.g. encoded in base2, n=O(log(k)), this enumeration takes O(sqrt(2)^(k)) time.
This thread is for the discussion of Less Wrong topics that have not appeared in recent posts. If a discussion gets unwieldy, celebrate by turning it into a top-level post.