A very interesting [Robertson-Seymour (graphs minors) theorem](http://en.wikipedia.org/wiki/Robertson-Seymour_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 *finite* collection $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 


1. it is indeed hard to test this property of a graph
2. the theorem does turn easily testable properties into long lists
3. 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$?
> 
> 
> 



How unhelpful is graph minors theorem?
For a reference concerning this problem, see [Cattell et al, "On computing graph minor obstruction sets", Theor. Comput. Sci. 2000](http://dx.doi.org/10.1016/S0304-3975%2897%2900300-9).


I think the answer to your specific question is that it's recursively enumerable (one can test all graphs using P to see whether they belong to E) but not recursive (without further information there is no way of knowing that one has found all obstructions).


Here's a specific construction that shows this: given an instance h of the halting problem, construct an algorithm A that either recognizes all graphs if h is a non-halting instance, or that recognizes the graphs with no K\_s minor if h halts in s steps. It's not hard to do this in such a way that A is always a polynomial time algorithm, but one can't tell whether E is empty or non-empty without solving the halting problem.


