However, this method requires a specific finite obstruction set to work, and the theorem does not provide one. The theorem proves that such a finite obstruction set exists, and therefore the problem is polynomial because of the above algorithm. However, the algorithm can be used in practice only if such a finite obstruction set is provided. As a result, the theorem proves that the problem can be solved in polynomial time, but does not provide a concrete polynomial-time algorithm for solving it. Such proofs of polynomiality are non-constructive: they prove polynomiality of problems without providing an explicit polynomial-time algorithm.[14] In many specific cases, checking whether a graph is in a given minor-closed family can be done more efficiently: for example, checking whether a graph is planar can be done in linear time.
Jump in the discussion.
No email address required.
Is there anything implying all encryption algos are equivalent to a graph minor problem? If not this is pretty meaningless.
Jump in the discussion.
No email address required.
P==NP
Jump in the discussion.
No email address required.
More options
Context
More options
Context