Can't you construct a problem from a known solution? To use an analogy, I can't factor arbitrarily large numbers in polynomial time, I'd doubt anyone else can either. But I can multiply large prime numbers together in polynomial time, so I can give someone a large composite and its factorization, because I started with the primes.