From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.emacs.gnus.general/80038 Path: news.gmane.org!not-for-mail From: Matthias Andree Newsgroups: gmane.emacs.gnus.general Subject: Re: pop3 speedup Date: Mon, 26 Sep 2011 22:09:39 +0200 Message-ID: <4E80DC03.2030706@dt.e-technik.uni-dortmund.de> References: <4E80CFAA.9050601@dt.e-technik.uni-dortmund.de> <87pqinw10i.fsf@gmail.com> <87zkhrulgw.fsf@gmail.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1317067811 4053 80.91.229.12 (26 Sep 2011 20:10:11 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 26 Sep 2011 20:10:11 +0000 (UTC) To: ding@gnus.org Original-X-From: ding-owner+M28332@lists.math.uh.edu Mon Sep 26 22:10:08 2011 Return-path: Envelope-to: ding-account@gmane.org Original-Received: from util0.math.uh.edu ([129.7.128.18]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1R8HV7-0006nO-ER for ding-account@gmane.org; Mon, 26 Sep 2011 22:10:05 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.math.uh.edu) by util0.math.uh.edu with smtp (Exim 4.63) (envelope-from ) id 1R8HUr-0004kp-G2; Mon, 26 Sep 2011 15:09:49 -0500 Original-Received: from mx2.math.uh.edu ([129.7.128.33]) by util0.math.uh.edu with esmtps (TLSv1:AES256-SHA:256) (Exim 4.63) (envelope-from ) id 1R8HUq-0004kf-Cu for ding@lists.math.uh.edu; Mon, 26 Sep 2011 15:09:48 -0500 Original-Received: from quimby.gnus.org ([80.91.231.51]) by mx2.math.uh.edu with esmtps (TLSv1:AES256-SHA:256) (Exim 4.76) (envelope-from ) id 1R8HUp-0003X4-J8 for ding@lists.math.uh.edu; Mon, 26 Sep 2011 15:09:48 -0500 Original-Received: from krusty.dt.e-technik.uni-dortmund.de ([129.217.163.1] helo=krusty.dt.e-technik.tu-dortmund.de) by quimby.gnus.org with esmtp (Exim 4.72) (envelope-from ) id 1R8HUo-0006Io-5B for ding@gnus.org; Mon, 26 Sep 2011 22:09:46 +0200 Original-Received: from [192.168.0.4] (g225194011.adsl.alicedsl.de [92.225.194.11]) by mail.dt.e-technik.tu-dortmund.de (Postfix) with ESMTPSA id DCD6B98366 for ; Mon, 26 Sep 2011 22:09:40 +0200 (CEST) User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:6.0.2) Gecko/20110902 Thunderbird/6.0.2 In-Reply-To: <87zkhrulgw.fsf@gmail.com> X-Spam-Score: -2.4 (--) List-ID: Precedence: bulk Xref: news.gmane.org gmane.emacs.gnus.general:80038 Archived-At: Am 26.09.2011 21:55, schrieb Antoine Levitt: > 26/09/11 21:35, Lars Magne Ingebrigtsen >> Antoine Levitt writes: >> >>> Nope, it's n^2, polynomial (1 + 2 + 3 + 4 ... + n is about n^2/2). >> >> Darn. > > Don't worry, you'll get it next time. > > (actually, it's pretty hard to do something exponentially on a list > structure. You'd have to run a non-trivial recursion. And then, of > course, find something to do with it.) The text book example of something recursing deeply and thus massively is the two-argument Ackermann function. Typical exponential problems are certain kinds of perfect optimization problems and quite a lot of scheduling problem classes, among them the travelling salesman problem. -- Matthias Andree