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

Text File | 1992-11-21 | 3.6 KB | 70 lines

Newsgroups: sci.crypt
Path: sparky!uunet!paladin.american.edu!europa.asd.contel.com!darwin.sura.net!udel!rochester!cantaloupe.srv.cs.cmu.edu!TINMAN.OZ.CS.CMU.EDU!jmount
From: [e-mail] (John Mount)
Subject: Re: Cryptography and P=NP
Message-ID: <[e-mail]>
Sender: [e-mail] (Usenet News System)
Nntp-Posting-Host: tinman.oz.cs.cmu.edu
Organization: Carnegie Mellon University
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
Distribution: inet
Date: Sat, 21 Nov 1992 17:56:03 GMT
Lines: 56

In article <[e-mail]>, [e-mail] (Stephen R. Tate) writes:
>In article <[e-mail]> [e-mail] (Jiri Sgall) writes:
>>So if you know that P=NP, you also have a polynomial algorithm for SAT that
>>either answers NO or gives you an satisfying assignment. You can do the same
>>for anything in NP.
>
>No, this is not true.   There are two *different* problems here:  knowing
>that P=NP, and having an algorithm for SAT (or any previously proved
>NP-complete problem, for that matter).   Don't forget the perfectly valid
>possibility that someone comes up with a non-constructive proof of P=NP ---
>this would be amazingly frustrating though.  Imagine knowing that P=NP, so you
>know that polynomial time algorithms exist for all problems in NP,
>but you don't know a polynomial time algorithm for any problem previously
>shown to be NP-complete!  I think that's what the original poster probably
>meant.

No- you are wrong.  Here is, roughly what Jiri was saying.

Assume an enumeration of all Turing machines.  Suppose we want to
solve SAT.  Let ALG be the Turing machine that simulates one step of
machine i every 2^i steps (so it runs machine 1 every other step, 2
every 4th , 4 every 8th).  If a machine being simulated ever halts ALG
checks if the output on the simulated tape is a satisfying assignment
for ALG's input formula- if so it halts in the accepting state.

Jiri's claim is that if P=NP then ALG accepts every satisfiable
formula in time polynomial in the input size (though it will not halt
on unsatisfiable formulae).

Why is this true?  Because if P=NP then by definition is a polynomial
p and a Turing machine j such that for every SAT formula x, j accepts
within x in time p(|x|) iff x is satisfiable (|x| = size of x in
bits).  (Even though the proof that P=NP may be nonconstructive and
not give an algorithm or even the polynomial p.)  In fact by the self
reducibility of problems in NP there must be a machine j' and a
polynomial p' such that for every SAT formula x, j' always halts
within time p'(|x|) and leaves a satisfying assignment on it's tape if
the formula was satisfiable.  Then it is not hard to see that ALG
accepts every satisfiable boolean formula in <= 2^j' p'(|x|) |x|
simulation steps.  (it is sufficient for the machine to run algorithm
j' for p'(|x|) steps- but it only runs alg j' once every 2^j' steps of
overall simulation- and may have to check an output from other
simulated Turing machines every step).  Now all this is true even if
you don't know j,j' or even p or p'!  Thus if P=NP the ALG is a Ptime
acceptor of satisfiable boolean formula- but you won't know why or how
long it is going to take.

The main weakness is the ALG can not deal with unsatisfiable assignment
(because you can not tell if it has run too long unless you know both
j and p).

--
--- It is kind of strange being in CS theory, given computers really do exist.
John Mount: [e-mail]               [phone]
School of Computer Science, Carnegie Mellon University,
5000 Forbes Ave., Pittsburgh PA 15213-3891