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

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

Xref: sparky sci.crypt:5024 sci.math:15260 comp.theory:2473
Newsgroups: sci.crypt,sci.math,comp.theory
Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen
From: [e-mail] (Larry Loen)
Subject: Re: Cryptography and P=NP
Sender: [e-mail]
Message-ID: <[e-mail]>
Date: Thu, 19 Nov 1992 19:30:36 GMT
Reply-To: [e-mail]
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
Nntp-Posting-Host: wo0z.rchland.ibm.com
Organization: IBM Rochester
Lines: 53

In article <[e-mail]>, [e-mail] (Seth Breidbart) writes:
|> 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.

Or is it, rather, P runs in polynomial time when it finds an answer?  I
realise this is very basic, but I have yet to have encountered any significant
sub-set of programs that are not trivial that can be counted on to 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.)
|>

Surely, it can't be this easy.  I get squeamish whenever I see clocks and
numbers on arguments of this kind.  Is the cardinality of the set of
P algorithms == number of natural numbers?  Why doesn't Cantor's diagonal
argument crop up somewhere and spoil everything?  (I don't necessarily mean
the original, but an appropriate analog of it).

Or, does the cardinality N (that is, of natural numbers)
arise elsewhere in this problem?  I suppose some really smart people have
already covered this ground; it is all very counter to my intuition.  Maybe
it's time for me to take a class on all of this stuff. . .

|> Seth        [e-mail]

--
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer