Article View: sci.crypt
Article #1943Re: Cryptography and P=NP
From: Piet van Oostrum
Date: Fri, 20 Nov 1992 09:05
Date: Fri, 20 Nov 1992 09:05
18 lines
1431 bytes
1431 bytes
>>>>> lwloen@rchland.vnet.ibm.com (Larry Loen) (LL) writes: LL> Surely, it can't be this easy. I get squeamish whenever I see clocks and LL> numbers on arguments of this kind. Is the cardinality of the set of LL> P algorithms == number of natural numbers? The set of all programs is countable. Each program is just a (finite) string in a programming language (e.g. Turing machines), and the set of finite strings over a finite alphabet is countable (order the strings lexicographically). LL> Why doesn't Cantor's diagonal LL> argument crop up somewhere and spoil everything? (I don't necessarily mean LL> the original, but an appropriate analog of it). Why should it? -- Piet van Oostrum <piet@cs.ruu.nl>
Technical Details
Message-ID:
<1992Nov20.090548.5840@cs.ruu.nl>Path:
arc1-ca.pugleaf.net!sparky!uunet!mcsun!sun4nl!ruuinf!pietReferences:
<1992Nov16.084503.10141@vax.oxford.ac.uk> <BxvEF3.Kqw.2@cs.cmu.edu> <1992Nov18.193900.20199@rchland.ibm.com> <1992Nov19.172719.1540@fid.morgan.com> <1992Nov19.193036.26711@rchland.ibm.com>Show Full Headers
Complete Article Headers
Newsgroups: sci.crypt,sci.math,comp.theory Path: arc1-ca.pugleaf.net!sparky!uunet!mcsun!sun4nl!ruuinf!piet From: piet@cs.ruu.nl (Piet van Oostrum) Subject: Re: Cryptography and P=NP Sender: network-news@cs.ruu.nl Message-ID: <1992Nov20.090548.5840@cs.ruu.nl> In-Reply-To: lwloen@rchland.vnet.ibm.com (Larry Loen) Date: Fri, 20 Nov 1992 09:05:48 GMT Reply-To: piet@cs.ruu.nl (Piet van Oostrum) References: <1992Nov16.084503.10141@vax.oxford.ac.uk> <BxvEF3.Kqw.2@cs.cmu.edu> <1992Nov18.193900.20199@rchland.ibm.com> <1992Nov19.172719.1540@fid.morgan.com> <1992Nov19.193036.26711@rchland.ibm.com> Organization: Dept of Computer Science, Utrecht University, The Netherlands Followup-To: sci.crypt Lines: 18