From: Franky Backeljauw Subject: Re: decision problems not in P Date: Mon, 30 Oct 2000 16:23:31 +0100 Newsgroups: comp.theory,sci.math Summary: [missing] David Bernier wrote: > > I'd be interested in knowing of examples of decision problems > that are not in P. Recently, an aritcle has been published in "Mathematical Intelligencer" which states that MineSweeper is NP-complete. I found this to be a very interesting article, because everybody knows the game, and has played it at least once. You can find more information on the authors website : http://www.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm ---------------------------------------------------------------- Franky Backeljauw franky.backeljauw@uia.ua.ac.be 2e Lic Wiskunde-Informatica http://fbackelj.dyns.cx Universiteit Antwerpen 03/820.24.16 ---------------------------------------------------------------- "A mathematician is a machine for turning coffee into theorems." Paul Erdos (1913-1996) ----------------------------------------------------------------