Re: best (known) polytime approximation algorithm for NP-complete problems?

On Dec 9, 4:14 am, Christian Siebert <ib...@xxxxxx> wrote:
cplxp...@xxxxxxxxx wrote:
I guess the (very vague) thing I'm going for is an NP-complete problem
for which if I map an instance of, say, integer factorization to the
problem, I could decide the instance in polynomial time and be
accurate more than 51% of the time.

Although the following algorithm runs in O(log N) time, it returns a
factor of a given big decimal integer N with a probability of 73%:

tryFactor(N):
   if (lastDigit(N) % 2) = 0 return '2 is a factor of N';
   if (digitSum(N) % 3) = 0 return '3 is a factor of N';
   if (lastDigit(N) % 5) = 0 return '5 is a factor of N';
   return 'no factor found'; // only 8/30 of all numbers reach this step

You see, it is easy to construct an integer factorization algorithm
which factors an input in polynomial time while being accurate for more
than 51% of all possible inputs.

    Christian


Yeah, good point I suppose. Thanks for pointing that out.

-Phil

.

Relevant Pages

  • Re: best (known) polytime approximation algorithm for NP-complete problems?
    ... it is easy to construct an integer factorization algorithm which factors an input in polynomial time while being accurate for more than 51% of all possible inputs. ... the question of the distribution of inputs. ... The same problem applies to the reduction idea. ...
    (comp.theory)
  • Re: best (known) polytime approximation algorithm for NP-complete problems?
    ... for which if I map an instance of, say, integer factorization to the ... it is easy to construct an integer factorization algorithm which factors an input in polynomial time while being accurate for more than 51% of all possible inputs. ...
    (comp.theory)
  • Re: Traveling salesman, idea, easy to program?
    ... everyone here would like a polynomial time solution to TSP.   ...    Let N be the number we want to factor. ... counting function. ... contact by email on this issue, then do even the most basic research ...
    (comp.lang.java.programmer)
  • Re: 6P=NP: Proof: Nondeterministic Algorithm
    ...     Nondeterministic algorithms have two phases: ... each time the algorithm is run the resulting guess may differ. ... be done in Oor polynomial time. ... sk) Î PAP, that is an tuple. ...
    (sci.math)