From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: 103376,9dfc10efb95ba130
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news1.google.com!news2.google.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!nx01.iad01.newshosting.com!newshosting.com!198.186.194.249.MISMATCH!transit3.readnews.com!news-xxxfer.readnews.com!news-out.readnews.com!postnews3.readnews.com!not-for-mail
Date: Sat, 11 Sep 2010 14:29:06 -0400
From: "Peter C. Chapin" <chapinp@acm.org>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US;
 rv:1.9.2.9) Gecko/20100825 Lightning/1.0b2 Thunderbird/3.1.3
MIME-Version: 1.0
Newsgroups: comp.lang.ada
Subject: Re: Inefficient algorithms
References: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
	<8f0nd6F8ucU1@mid.individual.net> <8f0o4uFct8U1@mid.individual.net>
 <87lj78ab6m.fsf@ludovic-brenta.org> <8f16vaF2q1U1@mid.individual.net>
In-Reply-To: <8f16vaF2q1U1@mid.individual.net>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Message-ID: <4c8bcae9$0$2400$4d3efbfe@news.sover.net>
Organization: SoVerNet (sover.net)
NNTP-Posting-Host: 25d93ffb.news.sover.net
X-Trace: 
 DXC=g[0?Fl3aB9ORZfJoa3=8@NK6_LM2JZB_CYHO@RciHi`C:WUUlR<856O\_cDWn30VlHG;Q:jlUQ]YE
X-Complaints-To: abuse@sover.net
Xref: g2news1.google.com comp.lang.ada:14016
Date: 2010-09-11T14:29:06-04:00
List-Id: <comp.lang.ada>

On 2010-09-11 07:20, Niklas Holsti wrote:

> This example is just the Boolean satisfiability problem (SAT), a
> well-known difficult problem, which is not trivial in the general case.

Indeed, SAT is NP-complete. I believe it may have been the first problem
proved to be NP-complete (not sure). So if P /= NP as many people
suspect, there is no polynomial time way of solving SAT.

Peter