(buttondown.com)

108 points BerislavLopac | 2 comments | 17 Apr 25 07:34 UTC | HN request time: 0.002s | source

Show context

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 #

1. macleginn ◴[17 Apr 25 15:32 UTC] No.43718347[source]▶

>>43716772 #

"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 #

2. dgs_sgd ◴[17 Apr 25 16:37 UTC] No.43719210[source]▶

>>43718347 (TP) #

I think that's unclear. A constructive proof of P != NP might yield insights into the "gap" between them.

↑

The Halting Problem is a terrible example of NP-Harder