I think P != NP is extremely interesting, but I wouldn't say it has strong implications for the nature of the concept of determinism or reality. I think that the idea of a Turing machine / the notion of computability has deep philosophical implications, but even that I wouldn't say has implications for "the nature of reality."

If you think that prime numbers are interesting, then I can tell you that GRH is the single most central conjecture in the study of prime numbers. Personally, I think prime numbers are some of the most fundamental and intrinsically interesting objects in pure math, but of course, this is subjective!