News for hackers. Stuff that matters.
Re:P vs. NP by btilly on Wednesday January 04, 2017 @01:25PM (#13320717)
In this case the polynomial time algorithm is to test the graph against a finite list of forbidden minors. This has a reasonable exponent, but a constant dependent upon how long that finite list is.

That finite list can be extremely long indeed. And in some cases, there is no way of finding or verifying the full list.

There are no comments on this comment yet.