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

Internet Message Format | 1992-11-21 | 3.4 KB

Xref: sparky sci.crypt:5158 sci.math:15346 comp.theory:2501
Newsgroups: sci.crypt,sci.math,comp.theory
Path: sparky!uunet!secapl!Cookie!frank
From: [e-mail] (Frank Adams)
Subject: Re: Cryptography and P=NP
Message-ID: <[e-mail]>
Date: Sat, 21 Nov 1992 19:19:44 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Organization: Security APL, Inc.
Lines: 55

In article <[e-mail]> [e-mail] writes:
>In article <[e-mail]>, [e-mail] (Seth Breidbart) writes:
>|> In article <[e-mail]>
>|> >Do all programs of class P halt?
>|>
>|> 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.

No; algorithms in P *must* halt in polynomial time.  A non-trivial set of
programs that can be counted on to halt is the set of programs which have
been proved to always halt.

One proves things in the first place about all programs in a class like P or
NP by taking an unspecified Turing machine which is assumed to implement a
program in the class.  One does a formal construction on that Turing
machine, and proves that, if it is in fact in the class, the construction
works.  (Once some basic theorems have been proved, it is rarely necessary
to return to this level.)

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

This construction contains a misstatement.  One is not numbering all the
polynomial-time machines; rather, the construction builds a sequence of
machines which will implement all polynomial-time algorithms.  (The set of
all polynomial-time machines is not effectively enumerable.)  However, by
taking *all* Turing machines, and modifying the kth one so that it halts
with failure if it would otherwise have taken more than time (n+1)^k, you
will get each polynomial-time algorithm.  (The quoted n^k has a problem with
n=1; this can be fixed more directly, but it does not affect the remainder of
the argument.) The key point is that every algorithm occurs infinitely often
in any effective list of all Turing machines; one can always add some extra
"overhead" to the machine.

(There is also a problem with the stated bound; given a problem in NP with a
non-deterministic time bound of n^j, if j > k, the actual bound will be
k n^j, not k n^k.)

Given a problem which actually is in NP, this universal machine will in fact
solve it in polynomial time if P=NP -- indeed, it will solve any problem in
P, given an NP formulation, in polynomial time.  If the NP problem is in not
in P, it will always halt, but will not necessarily run in polynomial time.

As a practical algorithm, it doesn't make it; a run time of O(n^10^20),
which could well happen, is not practical.