Re: Not constructive proof of existing of an algorithm

In article <1114169622.473811.249230@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Yajun <yalding@xxxxxxxxx> wrote:
>I somehow get the idea. Then we fall into another assumption that
>sounds intuitive:
>
>For fixed $d$, the set of "problematic subgraphs" can be computed in
>finite steps only depend on $d$.

No, I think you're missing the point. For the type of problems in
question, the set of problematic subgraphs is finite and *independent
of the input*. Therefore it doesn't matter how hard it is to *find* that
set (you might not know how to find the problematic set at all!); this
cannot affect the *complexity* of solving the problem, since complexity is
always measured as a function of the input.

Another way to put it is that the difficulty of finding the problematic
subgraphs affects the complexity of *finding the algorithm* for the
problem, which is entirely separate from the *complexity of the algorithm*
that you find.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.