[pekinb]

I may be mistaken, and this might require an exhaustive search of the relevant literature, but I believe 3SAT is NP-Complete and therefore this one example does indeed lead to the stated conclusion.