Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
Gordon Royle's user avatar
  • 12.7k