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

Internet Message Format | 1992-11-19 | 1.8 KB

Xref: sparky sci.crypt:5013 sci.math:15238 comp.theory:2469
Newsgroups: sci.crypt,sci.math,comp.theory
Path: sparky!uunet!s5!sethb
From: [e-mail] (Seth Breidbart)
Subject: Re: Cryptography and P=NP
Message-ID: <[e-mail]>
Organization: my opinions only
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Thu, 19 Nov 1992 17:27:19 GMT
Lines: 31

In article <[e-mail]>
[e-mail] writes:
>In article <[e-mail]> Jiri Sgall writes:
>
>>(partial quote of James Annan):
>
>>|> And remember, proving P=NP doesn't necessarily mean finding such an algorithm,
>>|> merely proving it exists.
>>|>
>
>>Once you have the proof, you can easily run a kind of universal algorithm,
>>which will be guaranteed to be polynomial
>
>OK, I don't know beans about P and NP.  So, an elementary question:
>
>Do all programs of class P halt?  Your "universal algorithm" seems perilously
>close to the "halting" problem and I have never been able to eliminate it
>from far simpler cases than P or NP.  Or, is the halting issue kind of a
>separate point/issue (ie, the solution is "P" when it works)?

Each program in P runs in polynomial time, so it must halt.

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.)

Seth        [e-mail]