Re: Cryptography and P=NP

Article View: sci.crypt

Article #1879

#1879

From: Larry Loen
Date: Wed, 18 Nov 1992 19:39

21 lines
1673 bytes

In article <BxvEF3.Kqw.2@cs.cmu.edu> 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)?

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

Technical Details

Message-ID: <1992Nov18.193900.20199@rchland.ibm.com>

Path:

arc1-ca.pugleaf.net!sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!malgudi.oar.net!news.ans.net!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen

References:

<1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com> <1e7fvdINN87s@iskut.ucs.ubc.ca> <1992Nov16.084503.10141@vax.oxford.ac.uk> <BxvEF3.Kqw.2@cs.cmu.edu>

Show Full Headers

Complete Article Headers

Newsgroups: sci.crypt,sci.math,comp.theory
Path: arc1-ca.pugleaf.net!sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!malgudi.oar.net!news.ans.net!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen
From: lwloen@rchland.vnet.ibm.com (Larry Loen)
Subject: Re: Cryptography and P=NP
Sender: news@rchland.ibm.com
Message-ID: <1992Nov18.193900.20199@rchland.ibm.com>
Date: Wed, 18 Nov 1992 19:39:00 GMT
Distribution: inet
Reply-To: lwloen@vnet.ibm.com
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com> <1e7fvdINN87s@iskut.ucs.ubc.ca> <1992Nov16.084503.10141@vax.oxford.ac.uk> <BxvEF3.Kqw.2@cs.cmu.edu>
Nntp-Posting-Host: wo0z.rchland.ibm.com
Organization: IBM Rochester
Lines: 21

Reply to Parent Message