Re: riemann hypothesis needed to factor numbers?

Ben Rudiak-Gould wrote:
I think that such algorithms would tend to be fast
in practice for the
same reason that the nontrivial zeros of the zeta
function are on the
critical line "in practice". A proof of RH would
only be useful for
proving an asymptotic efficiency bound.

As an amusing aside, for any problem, it's easy to
write an algorithm which
solves it in polynomial time if and only if a
polynomial-time algorithm for
that problem exists. You simply enumerate all
algorithms and run them in
parallel, running (say) step #s of algorithm #a in
pass s+a. If algorithm #A
(one-based) solves the problem in P(n) steps, this
algorithm will solve it
in at most 1/2 (A + P(n)) (A + P(n) - 1) steps, which
is another polynomial
in n. So if there are any polynomial-time factoring
algorithms, then we
already know one. Of course, A is likely to be pretty
large. Dang those
constant factors.

-- Ben

im sorry but thats BS !

if that were true
we could easily check P = NP since in your assumption testing P is easy (because finite possibilities (also incorrect btw ) )

tommy1729
.

Relevant Pages

  • P6 = NP (WAS: an oracle paradox)
    ... theory is the Turing machine,introduced by Alan Turing in 1936 ... solvable by some algorithm within anumber of steps bounded by some xed ... over .Then a language over is a subset L of. ... We say that R is polynomial-time i LR ...
    (sci.math)
  • P Versus NP
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • Re: Mr. P and Ms. S
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • Re: Math errors in book Secret Life of Numbers
    ... his students have proven that primes can be found in polynomial time. ... For practical purposes the algorithm is, admittedly, still too ... that in practice, it always was solved in polynomial time using the ... the simplex method is not a polynomial-time algorithm. ...
    (sci.math.research)
  • Re: question on complexity theorem proposition
    ... 2/ M does not terminates. ... The time bound for the simulation grows with the (size of   ... Assume there exists an algorithm ... polynomial-time execution of algorithms. ...
    (comp.theory)
Quantcast