Re: Not constructive proof of existing of an algorithm

On 2005-04-20, Iron Bone <iron.bone@xxxxx> wrote:
> Do you know a not constructive proof of existing of an algorithm
> ( polynomial time algorithm , ...).
>
> Mayby every proof of existing of an algorithm have to give information how
> write this algorithm.
>
> I.B.
>
>
> --
> Using Opera's revolutionary e-mail client: http://www.opera.com/m2/

There are problems in graph theory for which it is known that
a polynomial algorithm exists because there is a finite obstruction set
but the obstruction set is not known.
.

Relevant Pages

  • Re: Not constructive proof of existing of an algorithm
    ... finally prove that the "computation of the obstruction set" is NP-Hard? ... If there is no way in Polynomial timeto get the obstruction set, how can we say we can do something in polynomial time assuming the knowledge of obstruction set? ... 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 ...
    (comp.theory)
  • Not constructive proof of existing of an algorithm
    ... Do you know a not constructive proof of existing of an algorithm (polynomial time algorithm, ... Mayby every proof of existing of an algorithm have to give information how write this algorithm. ...
    (comp.theory)