Re: Not constructive proof of existing of an algorithm

Yajun wrote: 
I am confused during the reading of the description. How about one
finally prove that the "computation of the obstruction set" is NP-Hard?
If there is no way in Polynomial time(if P != NP) to get the
obstruction set, how can we say we can do something in polynomial time
assuming the knowledge of obstruction set?

The obstruction set usually is independent of the input but depends on some other parameter d. If your algorithm is required to solve the problem for fixed d, you can hardwire it into your algorithm. Consider for example the generalized version of Kuratovkis theorem: Loosely speaking, for fixed gender d, there is a finite set of "problematic subgraphs", that prevent a graph to be embeddable on surfaces of gender d.

Chris
.

Relevant Pages

  • Re: Not constructive proof of existing of an algorithm
    ... > Mayby every proof of existing of an algorithm have to give information how ... > Using Opera's revolutionary e-mail client: http://www.opera.com/m2/ ... a polynomial algorithm exists because there is a finite obstruction set ...
    (comp.theory)
  • Re: Not constructive proof of existing of an algorithm
    ... I am confused during the reading of the description. ... finally prove that the "computation of the obstruction set" is NP-Hard? ... how can we say we can do something in polynomial time ...
    (comp.theory)