A very interesting Robertson-Seymour (graphs minors) theorem says:

Any infinite collection of graphs $C$ with the property that if $G\in C $ then its minors also are has the form $\{$graphs $G$ that don't contain any $E_i\}$ for some

finitecollection $E = \{E_i\}$.

So, the theorem says that you could create a list of forbidden minors to find out if the graph is torically embeddable, but this doesn't help much, since the list is both not fully known and large.

I wonder whether the above difficulty is because

- it is indeed hard to test this property of a graph
- the theorem does turn easily testable properties into long lists
- it is not known how to effectively turn easily testable properties into lists

Here's the formal question:

Consider a polynomial algorithm $P$ that returns a yes/no question given a graph as an input and which always returns yes for minors of any graph for which it returns yes. There exists $E$, the exceptional list of a collection defined by $P$. What is known about the computability of the map $P\mapsto E$?