From lojban-out@lojban.org Sun Dec 09 18:05:04 2007 Return-Path: X-Sender: lojban-out@lojban.org X-Apparently-To: lojban@yahoogroups.com X-Received: (qmail 86419 invoked from network); 10 Dec 2007 02:05:03 -0000 X-Received: from unknown (66.218.67.95) by m47.grp.scd.yahoo.com with QMQP; 10 Dec 2007 02:05:03 -0000 X-Received: from unknown (HELO mail5.sea5.speakeasy.net) (69.17.117.7) by mta16.grp.scd.yahoo.com with SMTP; 10 Dec 2007 02:05:03 -0000 X-Received: (qmail 13206 invoked from network); 10 Dec 2007 02:04:59 -0000 X-Received: from chain.digitalkingdom.org ([64.81.66.169]) (envelope-sender ) by mail5.sea5.speakeasy.net (qmail-ldap-1.03) with AES256-SHA encrypted SMTP for ; 10 Dec 2007 02:04:59 -0000 X-Received: from lojban-out by chain.digitalkingdom.org with local (Exim 4.68) (envelope-from ) id 1J1Y0u-0003DY-JZ for lojban@yahoogroups.com; Sun, 09 Dec 2007 18:04:56 -0800 X-Received: from chain.digitalkingdom.org ([64.81.66.169]) by chain.digitalkingdom.org with esmtp (Exim 4.68) (envelope-from ) id 1J1Xzz-0002pG-EO; Sun, 09 Dec 2007 18:04:04 -0800 X-Received: with ECARTIS (v1.0.0; list lojban-list); Sun, 09 Dec 2007 18:01:59 -0800 (PST) X-Received: from nobody by chain.digitalkingdom.org with local (Exim 4.68) (envelope-from ) id 1J1Xy3-0002p9-5v for lojban-list-real@lojban.org; Sun, 09 Dec 2007 18:01:59 -0800 X-Received: from phma.optus.nu ([166.82.175.165] helo=ixazon.dynip.com) by chain.digitalkingdom.org with esmtp (Exim 4.68) (envelope-from ) id 1J1Xxz-0002oy-Bh for lojban-list@lojban.org; Sun, 09 Dec 2007 18:01:59 -0800 X-Received: from chausie (unknown [192.168.7.4]) by ixazon.dynip.com (Postfix) with ESMTP id 5D80ACE743 for ; Sun, 9 Dec 2007 21:01:53 -0500 (EST) Date: Sun, 9 Dec 2007 22:01:47 -0400 User-Agent: KMail/1.9.5 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200712092101.48093.phma@phma.optus.nu> X-Spam-Score: 0.1 X-Spam-Score-Int: 1 X-Spam-Bar: / X-archive-position: 13991 X-ecartis-version: Ecartis v1.0.0 Errors-to: lojban-list-bounce@lojban.org X-original-sender: phma@phma.optus.nu X-list: lojban-list X-Spam-Score: 0.1 X-Spam-Score-Int: 1 X-Spam-Bar: / To: lojban@yahoogroups.com X-Originating-IP: 69.17.117.7 X-eGroups-Msg-Info: 1:12:0:0:0 X-eGroups-From: Pierre Abbat From: Pierre Abbat Reply-To: phma@phma.optus.nu Subject: [lojban] How do I say "NP-complete"? X-Yahoo-Group-Post: member; u=116389790; y=iRO8-cHZeBar5Rd6cNawyD8LzR_qHwXFbw5Mk0gL1_G90oVfhQ X-Yahoo-Profile: lojban_out X-Yahoo-Message-Num: 28469 NP-complete problems are an important class of problems in computational complexity theory; they are those problems that can be solved in polynomial time by a nondeterministic algorithm and are at least as hard as any other NP problem. I'd like to say that in Lojban, but I'm running into some problems, hopefully not NP-hard ;) Nondeterministic isn't the same as probabilistic. Both kinds of algorithm can make random decisions, but the nondeterministic computer splits into several copies of itself, each making one of the possible alternatives, while the probabilistic computer just takes one alternative. For "probabilistic" I could just say {cunso}, but "nondeterministic" I'm not so sure. For "polynomial" I came up with {tefsujme'o}. "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. "Algorithm" could be translated by a fu'ivla {algoritmi} or a lujvo with {tadji}. The last problem (hopefully) is how to translate a compound of an initialism and a word. Of the interlanguage links on Wikipedia, all (including Arabic and Russian) use the letters "NP" except Serbian, which transliterates them to Cyrillic, and Thai, which I don't know how to read. What should we do in Lojban? Pierre 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.