Thank you for your answer. The Hamiltonian cycle in degree three graphs example is exactly what I was looking for.

@PeterTaylor your answer explains why it is logically incorrect for me to conclude that efficiently determining primality implies one can efficiently determine factorization. However, my intuition is still bothered by the observation.

@TimothyChow I remember having a similar conversation with you on Usenet a long time ago. As I recall, you gave the game Hex (or maybe someone else on the thread gave it?) as an example of such a problem. There is a winning strategy but it is too big to even specify and thus intractable to find. However, with factorization the factor is not too big to specify unlike Hex.

@JoelDavidHamkins it is true that there are trivial examples. I am looking for nontrivial examples that are similar to integer factorization.

What about religion?