←back to thread

The Halting Problem is a terrible example of NP-Harder

(buttondown.com)
108 points BerislavLopac | 3 comments | 17 Apr 25 07:34 UTC | HN request time: 0.689s | source
1. Leszek ◴[17 Apr 25 13:46 UTC] No.43716772[source]▶
Something I find fascinating is that we know that P != EXPTIME, and that P <= NP <= EXPTIME, but have managed to prove neither P != NP nor NP != EXPTIME. NP has to be somewhere between them but we have no idea where.
replies(1): >>43718347 #
2. macleginn ◴[17 Apr 25 15:32 UTC] No.43718347[source]▶
"NP has to be somewhere between them but we have no idea where" – I guess that this state of affairs won't change much even if we prove P != NP?
replies(1): >>43719210 #
3. dgs_sgd ◴[17 Apr 25 16:37 UTC] No.43719210[source]▶
I think that's unclear. A constructive proof of P != NP might yield insights into the "gap" between them.