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.