From: "Peter C. Chapin" <chapinp@acm.org>
Subject: Re: Inefficient algorithms
Date: Sat, 11 Sep 2010 14:29:06 -0400
Date: 2010-09-11T14:29:06-04:00 [thread overview]
Message-ID: <4c8bcae9$0$2400$4d3efbfe@news.sover.net> (raw)
In-Reply-To: <8f16vaF2q1U1@mid.individual.net>
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
next prev parent reply other threads:[~2010-09-11 18:29 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-09-11 4:24 Inefficient algorithms Rick
2010-09-11 6:51 ` J-P. Rosen
2010-09-13 3:45 ` Robert A Duff
2010-09-11 6:54 ` Niklas Holsti
2010-09-11 7:07 ` Niklas Holsti
2010-09-11 9:07 ` Rick
2010-09-11 15:05 ` Niklas Holsti
2010-09-17 5:26 ` Rick
2010-09-11 9:20 ` Ludovic Brenta
2010-09-11 9:23 ` Ludovic Brenta
2010-09-11 11:20 ` Niklas Holsti
2010-09-11 18:29 ` Peter C. Chapin [this message]
2010-09-11 14:28 ` stefan-lucks
2010-09-12 1:04 ` Wilson
2010-09-12 1:53 ` Rick
2010-09-12 8:35 ` Georg Bauhaus
2010-09-12 11:56 ` stefan-lucks
2010-09-15 1:11 ` BrianG
-- strict thread matches above, loose matches on Subject: below --
2010-09-15 8:51 Rick
2010-09-15 21:45 ` John B. Matthews
2010-09-16 12:05 ` Chad R. Meiners
2010-09-16 20:19 ` John B. Matthews
2010-09-17 5:24 ` Rick
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox