All Questions
Tagged with graph-minors computational-complexity
1 question
46
votes
8
answers
5k
views
Can a problem be simultaneously polynomial time and undecidable?
The Robertson-Seymour theorem on graph minors leads to some interesting conundrums.
The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...
- 12.7k