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@iki.fi>, aka decoy, student/math/Helsinki university