3 ms·
PRIMES, checking whether a number is a prime number or not. It's important to note that this happens literally all the time in research. There are hundreds of
by JohnKemeny 4y ago
PRIMES, checking whether a number is a prime number or not.
It's important to note that this happens literally all the time in research. There are hundreds of problems that are easily seen to be _in NP_, that we simply don't know whether or not is in P. Many of these problems aren't that interesting, though.
- adgjlsfhk1 4y agoPrimes is a really good example because half of the proof is trivial (if I give you a factor, you can verify compositeness trivially), but verifying the other half is a pretty big number theory rabbit hole.