<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html; charset=ISO-8859-1"
 http-equiv="Content-Type">
  <title></title>
</head>
<body text="#000000" bgcolor="#ffffff">
I might have a use for this, so I could give it a go.<br>
I'll have a look through this post in detail tomorrow morning.<br>
<br>
RS<br>
<br>
On 04/11/10 17:38, Simon Peyton-Jones wrote:
<blockquote
 cite="mid:59543203684B2244980D7E4057D5FBC11CFA8B3D@DB3EX14MBXC308.europe.corp.microsoft.com"
 type="cite">
  <meta http-equiv="Content-Type"
 content="text/html; charset=ISO-8859-1">
  <meta name="Generator" content="Microsoft Word 12 (filtered medium)">
  <style>
<!--
 /* Font Definitions */
 @font-face
        {font-family:"Cambria Math";
        panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:Tahoma;
        panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
        {font-family:Verdana;
        panose-1:2 11 6 4 3 5 4 4 2 4;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0cm;
        margin-bottom:.0001pt;
        font-size:11.0pt;
        font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
p.MsoAcetate, li.MsoAcetate, div.MsoAcetate
        {mso-style-priority:99;
        mso-style-link:"Balloon Text Char";
        margin:0cm;
        margin-bottom:.0001pt;
        font-size:8.0pt;
        font-family:"Tahoma","sans-serif";}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
        {mso-style-priority:34;
        margin-top:0cm;
        margin-right:0cm;
        margin-bottom:0cm;
        margin-left:36.0pt;
        margin-bottom:.0001pt;
        font-size:11.0pt;
        font-family:"Calibri","sans-serif";}
span.EmailStyle17
        {mso-style-type:personal-compose;
        font-family:"Verdana","sans-serif";
        color:windowtext;}
span.BalloonTextChar
        {mso-style-name:"Balloon Text Char";
        mso-style-priority:99;
        mso-style-link:"Balloon Text";
        font-family:"Tahoma","sans-serif";}
.MsoChpDefault
        {mso-style-type:export-only;}
@page WordSection1
        {size:612.0pt 792.0pt;
        margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
        {page:WordSection1;}
 /* List Definitions */
 @list l0
        {mso-list-id:582643434;
        mso-list-type:hybrid;
        mso-list-template-ids:153270398 949516180 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
        {mso-level-text:"\(%1\)";
        mso-level-tab-stop:none;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
@list l0:level2
        {mso-level-tab-stop:72.0pt;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
@list l0:level3
        {mso-level-tab-stop:108.0pt;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
@list l0:level4
        {mso-level-tab-stop:144.0pt;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
@list l0:level5
        {mso-level-tab-stop:180.0pt;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
@list l0:level6
        {mso-level-tab-stop:216.0pt;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
@list l0:level7
        {mso-level-tab-stop:252.0pt;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
@list l0:level8
        {mso-level-tab-stop:288.0pt;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
@list l0:level9
        {mso-level-tab-stop:324.0pt;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
ol
        {margin-bottom:0cm;}
ul
        {margin-bottom:0cm;}
-->
  </style><!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1" />
 </o:shapelayout></xml><![endif]-->
  <div class="WordSection1">
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;">Hi Cafe<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;">A while back there was a
  <a moz-do-not-send="true"
 href="http://www.mail-archive.com/haskell-cafe@haskell.org/msg79633.html">thread</a>
about a good implementation of a (pseudo) random number generator with
a good &#8220;split&#8221; operation.&nbsp; There&#8217;s lots of material on generators that
generate a linear
  <b>sequence</b> of random numbers, but much less on how to generate a
  <b>tree</b> of random numbers, which is what Haskell&#8217;s System.Random
API requires.<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;">I happened to meet Burton
Smith recently, who wrote some early papers about this stuff (eg &#8220;<a
 moz-do-not-send="true"
 href="http://portal.acm.org/citation.cfm?id=1746034">Pseudo random
trees in Monte-Carlo</a>&#8221;), so I asked him. <o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;">His reply is below, along
with some follow-up comments from his colleagues Tolga Acar and Gideon
Yuval. &nbsp;&nbsp;The generator uses crypto functions, so it&#8217;s probably more
computationally expensive than common linear-sequence generators, but
in exchange you get robust splitting.<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;">Does anyone feel like
taking the idea and turning it into a Haskell library?&nbsp; &nbsp;(Or even a
Haskell Wiki page?)&nbsp; I&#8217;m taking the liberty of cross-posting to the
libraries list.<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;">Simon<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US">From:</span></b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US"> Burton Smith
  <br>
  <b>Sent:</b> Tuesday, November 02, 2010 3:58 PM<br>
  <b>To:</b> Simon Peyton-Jones<br>
  <b>Cc:</b> Gideon Yuval (Gideon Yuval); Tolga Acar<br>
  <b>Subject:</b> Random number generation<o:p></o:p></span></p>
  <p class="MsoNormal"><span lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span lang="EN-US">With some help from Gideon
and Tolga, I think the solution to the &#8220;arbitrary tree of random
numbers problem&#8221; is as follows:<o:p></o:p></span></p>
  <p class="MsoNormal"><span lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span lang="EN-US">The generator G is a pair
comprising a crypto key G.k and an integer counter (the &#8220;message&#8221;)
G.c.&nbsp; The (next G) operation returns a pair: 1. a random integer r
obtained by encrypting G.c with G.k, and 2. a new generator G&#8217; such
that G&#8217;.k = G.k and G&#8217;.c = G.c + 1.&nbsp; The (split G) operation is
similar, returning the same G&#8217;, except that instead of returning a
random integer r it returns a third generator G&#8217;&#8217; such that G&#8217;&#8217;.k = r
and G&#8217;&#8217;.c = 0.<o:p></o:p></span></p>
  <p class="MsoNormal"><span lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span lang="EN-US">A suitable block cipher
system might be 128-bit AES (Rijndael).&nbsp; Unencumbered implementations
exist in a variety of languages, and performance is pretty good and
will improve dramatically as hardware support improves.&nbsp; I&#8217;d pick both
crypto key size and the size of the result r to be 128 bits, and employ
a &nbsp;64 bit counter c.&nbsp; Other crypto options exist.<o:p></o:p></span></p>
  <p class="MsoNormal"><span lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US">From:</span></b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US"> Simon Peyton-Jones
  <br>
  <b>Sent:</b> Wednesday, November 03, 2010 3:11 AM<br>
  <b>To:</b> Burton Smith; Gideon Yuval (Gideon Yuval)<br>
  <b>Cc:</b> Tolga Acar; Simon Peyton-Jones<br>
  <b>Subject:</b> RE: Random number generation<o:p></o:p></span></p>
  <p class="MsoNormal"><span lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-size: 9pt; font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;; color: rgb(31, 73, 125);">Burton,
Gideon, Tolga<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-size: 9pt; font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;; color: rgb(31, 73, 125);"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-size: 9pt; font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;; color: rgb(31, 73, 125);">Aha,
that&#8217;s interesting.&nbsp;&nbsp; I&#8217;d never seen a random number generator based on
crypto, but it seems like an attractive idea.&nbsp; As I understand it,
successive calls to &#8216;next&#8217; will give you<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-size: 9pt; font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;; color: rgb(31, 73, 125);">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
encrypt(0), encrypt(1), encrypt(2), encrypt(3),....<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-size: 9pt; font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;; color: rgb(31, 73, 125);"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-size: 9pt; font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;; color: rgb(31, 73, 125);">Is
this standard?&nbsp; Does it have provably good randomness properties,
(cycle length, what else?) like other RNGs?&nbsp; Or does it simply seem
very plausible?<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-size: 9pt; font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;; color: rgb(31, 73, 125);"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-size: 9pt; font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;; color: rgb(31, 73, 125);">Can
I send it round to the Haskell mailing list, in the hope that someone
will turn the idea into a library?&nbsp;&nbsp; (Ideally I&#8217;d like to make claims
about the randomness properties in doing so, hence my qns above.)<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US">From:</span></b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US"> Gideon Yuval (Gideon Yuval)
  <br>
  <b>Sent:</b> Wednesday, November 03, 2010 7:15 AM<br>
  <b>To:</b> Simon Peyton-Jones; Burton Smith<br>
  <b>Cc:</b> Tolga Acar<br>
  <b>Subject:</b> RE: Random number generation<o:p></o:p></span></p>
  <p class="MsoNormal"><span lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US">As long as the key, and the non-counting part of the
counter, are kept&#8221; secret&#8221;, anyone who can distinguish these
pseudorandoms from real random, in less than 2^128 steps, has a nice
paper for crypto-2011 (this is known as &#8220;provable security&#8221;) concerning
a weakness in AES128.<o:p></o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US">One exception: real randoms have a birthday paradox; the
pseudorandoms suggested do not. If you care, you can:<o:p></o:p></span></p>
  <p class="MsoListParagraph" style="text-indent: -18pt;"><!--[if !supportLists]--><span
 style="color: rgb(31, 73, 125);" lang="EN-US"><span style="">(1)<span
 style="font-family: &quot;Times New Roman&quot;; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal; -x-system-font: none;">&nbsp;&nbsp;&nbsp;
  </span></span></span><!--[endif]--><span
 style="color: rgb(31, 73, 125);" lang="EN-US">Limit the counter to
2^32 steps (paradox has 2^-64 probability) or even 2^16 (2^-96), then
rekey; or<o:p></o:p></span></p>
  <p class="MsoListParagraph" style="text-indent: -18pt;"><!--[if !supportLists]--><span
 style="color: rgb(31, 73, 125);" lang="EN-US"><span style="">(2)<span
 style="font-family: &quot;Times New Roman&quot;; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal; -x-system-font: none;">&nbsp;&nbsp;&nbsp;
  </span></span></span><!--[endif]--><span
 style="color: rgb(31, 73, 125);" lang="EN-US">XOR 2 such encrypted
counters, with different keys; or<o:p></o:p></span></p>
  <p class="MsoListParagraph" style="text-indent: -18pt;"><!--[if !supportLists]--><span
 style="color: rgb(31, 73, 125);" lang="EN-US"><span style="">(3)<span
 style="font-family: &quot;Times New Roman&quot;; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal; -x-system-font: none;">&nbsp;&nbsp;&nbsp;
  </span></span></span><!--[endif]--><span
 style="color: rgb(31, 73, 125);" lang="EN-US">XOR </span>
  <b><u><span style="color: red;" lang="EN-US">3</span></u></b><span
 style="color: rgb(31, 73, 125);" lang="EN-US"> successive values for
the same counter (just possibly cheaper; top-of-head idea).<o:p></o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US">More hard-core: swap the position of key &amp; message:
encrypting a constant &#8220;secret&#8221; with 1,2,3,4&#8230;. Gives pseudorandoms with
  </span><b><u><span style="color: red;" lang="EN-US">no</span></u></b><span
 style="color: rgb(31, 73, 125);" lang="EN-US"> birthday paradox.<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US">From:</span></b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US"> Tolga Acar
  <br>
  <b>Sent:</b> 03 November 2010 15:50<br>
  <b>To:</b> Gideon Yuval (Gideon Yuval); Simon Peyton-Jones; Burton
Smith<br>
  <b>Subject:</b> RE: Random number generation<o:p></o:p></span></p>
  <p class="MsoNormal"><o:p>&nbsp;</o:p></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US">Simon,<o:p></o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US">The general idea is not really that new in the crypto
area with constraints Gideon describes, of course. That is typically
called a PRNG &#8211; Pseudo Random Number Generator, or in another parlance,
Deterministic Random Bit Generators (DRBG). The DRBG constructions
based on hash functions and block ciphers are even standardized in NIST
publication SP800-90 (even though I may not recommend every one of
them).<o:p></o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US">As for the construction below, that is based on the AES
block cipher, that essentially takes advantage of the PRP (Pseudo
Random Permutation) property of the AES block cipher, as each block
cipher ought to be. So, as Gideon outlines below, if you fix the key,
the PRP gives you a random-looking (or, in other terms,
indistinguishable from random) output that no one without the secret
key and the &#8220;state&#8221; can generate or easily predict. Assuming an ideal
cipher (and AES is a close approximation to it), the probability is
believed to be the birthday paradox - no counterexample or a proof
exists without assumptions; so we stick to the birthday bound.<o:p></o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US">There ought to be papers on this somewhere. If not, that
condensed information is spread across many papers and is part of the
crypto folklore, I&#8217;d say.<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  <p class="MsoNormal"><b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US">From:</span></b><span
 style="font-size: 10pt; font-family: &quot;Tahoma&quot;,&quot;sans-serif&quot;;"
 lang="EN-US"> Burton Smith
  <br>
  <b>Sent:</b> 03 November 2010 19:03<br>
  <b>To:</b> Simon Peyton-Jones<br>
  <b>Cc:</b> Gideon Yuval (Gideon Yuval); Tolga Acar<br>
  <b>Subject:</b> RE: Random number generation<o:p></o:p></span></p>
  <p class="MsoNormal"><o:p>&nbsp;</o:p></p>
  <p class="MsoNormal"><span style="color: rgb(31, 73, 125);"
 lang="EN-US">Just two points of further clarification:<o:p></o:p></span></p>
  <p class="MsoListParagraph" style="text-indent: -18pt;"><span
 style="color: rgb(31, 73, 125);" lang="EN-US">1.</span><span
 style="font-size: 7pt; font-family: &quot;Times New Roman&quot;,&quot;serif&quot;; color: rgb(31, 73, 125);"
 lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  </span><span style="color: rgb(31, 73, 125);" lang="EN-US">&nbsp;All PRNGs
used in the technical computing space fail the birthday paradox
criterion (<i>i.e.
  </i>have full period), so we really need not worry about this.&nbsp; Also,
there are other mitigating factors,
  <i>e.g.</i> suppose we are using the PRNG to generate pseudorandom
residues mod n &lt;&lt; 2^128; the paradox is happily present there.<o:p></o:p></span></p>
  <p class="MsoListParagraph" style="text-indent: -18pt;"><span
 style="color: rgb(31, 73, 125);" lang="EN-US">2.</span><span
 style="font-size: 7pt; font-family: &quot;Times New Roman&quot;,&quot;serif&quot;; color: rgb(31, 73, 125);"
 lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
  </span><span style="color: rgb(31, 73, 125);" lang="EN-US">The big
innovation in this scheme is that the rekeying operation done by split
creates a new generator with &nbsp;independence guaranteed by &#8220;provable
security&#8221; in the sense Gideon mentioned &#8211; if someone can find something
nonrandom in the correlation between G&#8217; and G&#8217;&#8217;, say, then it amounts
to a weakness in AES128 and is publishable.&nbsp; So it&#8217;s yet another
example of reducibility, common in our field: &#8220;if you can easily
transform a known/famous hard problem P into this other problem Q, Q
must be hard&#8221;.<o:p></o:p></span></p>
  <p class="MsoNormal"><span
 style="font-family: &quot;Verdana&quot;,&quot;sans-serif&quot;;"><o:p>&nbsp;</o:p></span></p>
  </div>
  <pre wrap="">
<fieldset class="mimeAttachmentHeader"></fieldset>
_______________________________________________
Haskell-Cafe mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a>
  </pre>
</blockquote>
<br>
</body>
</html>