NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/sci/crypt/5211

Internet Message Format | 1992-11-23 | 1.7 KB

Xref: sparky sci.crypt:5211 sci.math:15428 comp.theory:2518
Path: sparky!uunet!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!usc!sdd.hp.com!saimiri.primate.wisc.edu!relay!relay2!tecsun1!zogwarg!hoey
From: [e-mail] (Dan Hoey)
Newsgroups: sci.crypt,sci.math,comp.theory
Subject: Re: Cryptography and P=NP
Message-ID: <[e-mail]>
Date: 23 Nov 92 18:52:33 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Followup-To: comp.theory
Organization: Naval Research Laboratory, Washington, DC
Lines: 25

With regard to the question of whether a proof for P=NP would yield a
polynomial-time algorithm for NP problems,

[e-mail] (Seth Breidbart) writes:

>Number all the polynomial-time machines (by adding a clock to each
>Turing Machine); do this in such a way that machine k runs in time < n^k.
>The "universal algorithm" consists of running machine i until it halts,
>and checking to see if an answer is found.  If machine k solves the
>problem, then this algorithm runs in time k n^k.  If P != NP, then
>this universal machine might not halt.  (More likely, it will always
>halt, but not within any polynomial time bound.)

Yes, P=NP implies such a machine i exists.  But you might not be able
to prove it can recognize an NP-complete language, in spite of the
fact that it does.  In fact, you might not be able to prove of any
particular machine that it recognizes an NP-complete language in
polynomial time.

You might not even be able to prove of any particular polynomial that
it is the time bound for such a machine, even though you have proven
that the machine and the polynomial must exist.

Dan Hoey
[e-mail]