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


To be honest, I was looking for the "best" algorithm because I
essentially figured it wouldn't be good enough, but was curious about
trying it anyway (if I have time, I may take your suggestion and try
it myself). My motivation is related to a Turing reduction of a
restricted case of the discrete logarithm problem I found to a
decision problem about 2 or 3 years ago. I was always curious if
there wasn't some algorithm that could decide this version of DLP with
51% accuracy or better. The reason why such accuracy would be
sufficient to effectively resolve the problem is this: the discrete
logarithm problem deals with an algebraic structure, and so it's
possible to generate "new" instances of DLP in a manner that may
appear random, but such that the new instances are tied to the old
instance.

I'm not very good at explaining this (particularly since it's been a
while since I dealt with any of this subject matter) but let me give
it a shot: Suppose we're dealing with DL(a), where "DL(x)" means "the
discrete logarithm of x (with fixed g and p)." (Note that p is a safe
prime and g is a generator for Z_p.) If you have DL(a) for some fixed
a, it's possible to say:

DL(a*b (mod p)) = DL(a) + DL(b) (mod (p-1))

Thus, if we want to calculate a DL that is close to DL(a), we can say:

DL(a*invDL(3) (mod p)) = DL(a) + DL(invDL(3)) (mod (p-1)) = DL (a) + 3
(mod (p-1))

(where invDL is the inverse discrete logarithm, or modular
exponentiation).

Since it's easy to calculate inverse discrete logarithms using
Montgomery multiplication, we can say that through this process, we
basically get a new (but unknown) discrete logarithm: DL(a*invDL
(3)). If we calculate that DL, then we can relate it back to DL(a),
since we know the precise value of DL(invDL(3))...it's just 3. In
other words, DL(a*invDL(3)) - 3 = DL(a). If we calculate one, we get
the other.

The decision problem I reduced DLP to is this:

Given a safe prime p, a generator for Z_p g, and an element a of Z_p:
Is DL(a) a member of the set {[1], [2], [3], ... [(p-1)/2]} ?

In other words, is a given DL in the "first half" of the set of
values, or in the second half?

So the idea is, if we wanted to solve this decision problem, we could
find a "close" value of the DL that is very near the a-value, reduce
it to an instance of 3SAT, use the algorithm that Tim mentioned (this
is the part, of course, that may not work), and repeat the process
several times--finding different "nearby discrete logarithms" and
running the algorithm on them--until we have a significant statistical
bias in favor of one answer to the question or the other.

I have no idea if this would work, and I suspect that it wouldn't,
which is why I'm hesitant to invest the time in trying to program it
until I have a fair chunk of free time.

I have a feeling I didn't explain that very well, but I hope it was at
least somewhat clear.

----

So, to put it briefly: I was interested in the best algorithm just
because I wanted to find the one that was most likely to work. All of
your points are well-taken. I'm not optimistic at all that this
algorithm would work on discrete logarithms.

-Phil


.

Relevant Pages