3 ms·
GI is not NP-Complete, rather it lives in the intermediary, somewhere between P and NP-Complete, of which there are only a few remaining problems many of which
by leecarraher 11y ago
GI is not NP-Complete, rather it lives in the intermediary, somewhere between P and NP-Complete, of which there are only a few remaining problems many of which shown to be solvable in P. What is interesting, from an everyday math enthusiast perspective is that the intermediate problems between P and NP-complete seem to be getting re-categorized to one or the other classes which optimistically suggests there may be no intermediate at all.