Technically you could solve the problem testing a polynomial number of solutions after spending super-polynomial time choosing the solutions to test.