|
|
|
|
|
|
by CJefferson
2069 days ago
|
|
|
The gap is small, and they might close it. P not being NP doesn't mean any individual problem is hard. A good, related problem is graph isomorphism (check if two graphs are the same, just with the vertices in a different order). The complexity of this isn't known, it's between P and NO at the moment. However, it's VERY hard to make hard instances. Basically all real world, or randomly generated, graphs can be solved in about O(n^3) time. There is significant research into just finding the hard cases. |
|
|