Here’s one candidate reason for P vs NP: the hard instances of any NPC problem are often the same as the hard instances of any other NPC problem, including a (yet to be formalized) problem that will turn equivalent to proving P vs NP. Then, it’s hard to prove almost by definition.
Here’s one candidate reason for P vs NP: the hard instances of any NPC problem are often the same as the hard instances of any other NPC problem, including a (yet to be formalized) problem that will turn equivalent to proving P vs NP. Then, it’s hard to prove almost by definition.