Ok, but how long did it take to find a polynomial algorithm for primality checking (published in 2002)? [1] And NP-complete problems are even harder than that! The history of mathematics is rife with conjectures that would be considered true if viewed "scientifically", but have an extremely large counterexample that disproves the whole thing. [2]
[1] https://en.wikipedia.org/wiki/AKS_primality_test [2] https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture