Re: Not constructive proof of existing of an algorithm

Iron Bone wrote:
Do you know a not constructive proof of existing of an algorithm ( polynomial time algorithm , ...). 

Consider the function

          / 1, if at least x consecutive `5' appear in the decimal expansion
          |    of pi = 3.141592653...;
   f(x) = |
          |
          \ 0, otherwise.

There certainly exist an algorithm that computes this function.
It is given either by the constant function

(*)   f(x) = 1,

if the decimal expansion of pi contains sequences of consecutive
`5' of any length, or, for some natural number k, by the function

             / 1, if x <= k;
             |
(**)  f(x) = |
             |
             \ 0, otherwise.

The proof is not constructive because (unless there have been recent
advances in number theory of which I am unaware) we don't know whether
the right algorithm is (*) or is of the form (**).  In the latter case,
we don't even know the value of k.  This doesn't matter, as long
as we only care about the existence of an algorithm.

Compare with the situation we have with function

          / 1, if _exactly_ x consecutive `5' appear in the decimal expansion
          |    of pi = 3.141592653...;
   g(x) = |
          |
          \ 0, otherwise.


In this case, unless there have been recent advances in number theory
of which I am unaware, we have no idea about whether an algorithm
for computing `g' exists or not.
Hope this helps,

     Roberto

--
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara@xxxxxxxxxxx
.

Relevant Pages

  • Re: RSA Challenge Question
    ... This might seem like a silly question but I wanted to know ... unless the algorithm required some deep ... friend of a friend of a friend of someone who worked at RSA suddenly ...
    (sci.crypt)
  • Re: RSA Challenge Question
    ... unless the algorithm required some deep ... talking about the case where integer factorization for any size ... The public keys gives the temporary private key ...
    (sci.crypt)
  • Re: RSA Challenge Question
    ... Would they be forced to live the rest of their lives in ... Mostra testo tra virgolette - ... I would put the algorithm for auction .. ...
    (sci.crypt)
  • Re: P = NP!
    ... develop a polynomial time algorithm for solving ... Newbie ... ... The OP suggests we try the algorithm for ourselves. ... Factoring is a good one, ...
    (sci.math)