CDR: Re: why should it be trusted?

Sampo A Syreeni ssyreeni at cc.helsinki.fi
Wed Oct 18 02:23:08 PDT 2000


On Tue, 17 Oct 2000, Riad S. Wahby wrote:

>While I agree that the limitations of current techniques do not
>dictate what is possible, it _is_ possible to show that a certain
>problem has a best-case order of growth (for something simple, think
>of gate-level addition; its best case is provably Theta(log(N)) ).

I think addition is bounded by something more like o(n) - carry propagation
limits it. Anyway, your point is accurate. There are proven NP-hard problems
and there have even been attempts to find ones with easy inverses for use in
crypto. I don't think any of them have succeeded.

>In this case, what Tim means is that work is being done towards
>showing that the best-case order of growth for factorization is faster
>than polynomial, hence it is NP-hard.

Quite. However, there are some things that must be considered if we're
really paranoid. For example, it is well known that the usual model of a
deterministic Turing machine does not always bound the complexity of a
problem 'nicely' even if current serial machines are used. Certain string
matching algorithms, for instance, can be proved to be in Theta(n log
n) if only binary comparison is used even while solutions exist in Theta(n
(log n)^a) with a less than 1 when the full ordering properties of the
problem can be exploited. That is the sort of stuff which makes one wonder
whether using radically different basic operations (like the ones based on
holography, which I do not think have been proven to be strictly equal to a
serial, polynomial time computation) could perhaps make a difference more
pronounced than simply taking care of a fixed number of orders in
complexity.

But I stray. Currently the extraordinary evidence simply isn't there. Even
if one has to be careful about making overbroad conclusions based on today's
theory of computation, it is highly unlikely that e.g. dramatically
accelerated factorization would currently or even in the future exist.

Sampo Syreeni <decoy at iki.fi>, aka decoy, student/math/Helsinki university





More information about the cypherpunks-legacy mailing list