From lojban-out@lojban.org Mon Dec 10 01:22:52 2007 Return-Path: X-Sender: lojban-out@lojban.org X-Apparently-To: lojban@yahoogroups.com X-Received: (qmail 47015 invoked from network); 10 Dec 2007 09:22:51 -0000 X-Received: from unknown (66.218.67.94) by m42.grp.scd.yahoo.com with QMQP; 10 Dec 2007 09:22:51 -0000 X-Received: from unknown (HELO mail8.sea5.speakeasy.net) (69.17.117.10) by mta15.grp.scd.yahoo.com with SMTP; 10 Dec 2007 09:22:51 -0000 X-Received: (qmail 9196 invoked from network); 10 Dec 2007 09:22:48 -0000 X-Received: from chain.digitalkingdom.org ([64.81.66.169]) (envelope-sender ) by mail8.sea5.speakeasy.net (qmail-ldap-1.03) with AES256-SHA encrypted SMTP for ; 10 Dec 2007 09:22:48 -0000 X-Received: from lojban-out by chain.digitalkingdom.org with local (Exim 4.68) (envelope-from ) id 1J1eqa-0002KI-GC for lojban@yahoogroups.com; Mon, 10 Dec 2007 01:22:44 -0800 X-Received: from chain.digitalkingdom.org ([64.81.66.169]) by chain.digitalkingdom.org with esmtp (Exim 4.68) (envelope-from ) id 1J1eqC-0002Hd-J9; Mon, 10 Dec 2007 01:22:24 -0800 X-Received: with ECARTIS (v1.0.0; list lojban-list); Mon, 10 Dec 2007 01:20:35 -0800 (PST) X-Received: from nobody by chain.digitalkingdom.org with local (Exim 4.68) (envelope-from ) id 1J1eoT-0002HT-0L for lojban-list-real@lojban.org; Mon, 10 Dec 2007 01:20:34 -0800 X-Received: from nf-out-0910.google.com ([64.233.182.186]) by chain.digitalkingdom.org with esmtp (Exim 4.68) (envelope-from ) id 1J1eoI-0002H2-I3 for lojban-list@lojban.org; Mon, 10 Dec 2007 01:20:32 -0800 X-Received: by nf-out-0910.google.com with SMTP id 4so2291265nfv for ; Mon, 10 Dec 2007 01:20:20 -0800 (PST) X-Received: by 10.86.73.17 with SMTP id v17mr5359607fga.1197278420174; Mon, 10 Dec 2007 01:20:20 -0800 (PST) X-Received: by 10.86.71.13 with HTTP; Mon, 10 Dec 2007 01:20:20 -0800 (PST) Message-ID: <3ccac5f10712100120o65fbb3pa2c67013fce5497e@mail.gmail.com> Date: Mon, 10 Dec 2007 12:20:20 +0300 In-Reply-To: <200712092101.48093.phma@phma.optus.nu> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <200712092101.48093.phma@phma.optus.nu> X-Google-Sender-Auth: 356abb0a2ce471cc X-Spam-Score: -0.0 X-Spam-Score-Int: 0 X-Spam-Bar: / X-archive-position: 13992 X-ecartis-version: Ecartis v1.0.0 Errors-to: lojban-list-bounce@lojban.org X-original-sender: slobin@ice.ru X-list: lojban-list X-Spam-Score: 0.0 X-Spam-Score-Int: 0 X-Spam-Bar: / To: lojban@yahoogroups.com X-Originating-IP: 69.17.117.10 X-eGroups-Msg-Info: 1:12:0:0:0 X-eGroups-From: "Cyril Slobin" From: "Cyril Slobin" Reply-To: slobin@ice.ru Subject: [lojban] Re: How do I say "NP-complete"? X-Yahoo-Group-Post: member; u=116389790; y=9uvnNZKoANIbEN5K9MDoDOxoTHVcbk6BMqxEa_orCDU9HukmGw X-Yahoo-Profile: lojban_out X-Yahoo-Message-Num: 28470 On 12/10/07, Pierre Abbat wrote: > "Complete" here does not have its usual meaning, so I don't think {mulno} is > appropriate. It means that any other problem in NP can be converted into an > instance of an NP-complete problem in polynomial time, so they are the > hardest possible NP problems. I opine "complete" means "sufficient" here, so {banzu}. The problem such that its solution is sufficient to solve any other NP-problem. -- Cyril Slobin `When I use a word,' Humpty Dumpty said, http://wagner.pp.ru/~slobin/ `it means just what I choose it to mean' To unsubscribe from this list, send mail to lojban-list-request@lojban.org with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if you're really stuck, send mail to secretary@lojban.org for help.