From: David A Molnar <dmolnar@fas.harvard.edu>
Subject: Re: decision problems not in P
Date: 30 Oct 2000 15:26:12 GMT
Newsgroups: comp.theory,sci.math
Summary: [missing]

In comp.theory Franky Backeljauw <franky.backeljauw@uia.ua.ac.be> wrote:
> 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 only problem is that we don't know for sure that NP != P. 

Better examples might be EXP-complete problems like various kinds of
testing regular expression equivalence. Papadimitriou's book
_Computational Complexity_ (which I don't have near me at the moment)
gives a list of some such problems and their variants.

Thanks, 
-David
==============================================================================

From: David Bernier <bernier@my-deja.com>
Subject: Re: decision problems not in P
Date: Tue, 31 Oct 2000 08:10:00 GMT
Newsgroups: comp.theory,sci.math

In article <8tk3uk$bv1$1@news.fas.harvard.edu>,
  David A Molnar <dmolnar@fas.harvard.edu> wrote:
> In comp.theory Franky Backeljauw <franky.backeljauw@uia.ua.ac.be> wrote:
> > 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 only problem is that we don't know for sure that NP != P.
>
> Better examples might be EXP-complete problems like various kinds of
> testing regular expression equivalence. Papadimitriou's book
> _Computational Complexity_ (which I don't have near me at the moment)
> gives a list of some such problems and their variants.

Thanks.  I did a Web search on exponential time, and a paper that
is often cited is by Hartmanis ans Stearns:

J. Hartmanis and R. Stearns: ``On the computational complexity of
       algorithms",   Trans. Amer. Math. Soc., 117:285--306, 1965.

David Bernier


Sent via Deja.com http://www.deja.com/
Before you buy.
==============================================================================

From: Isaac Kar-Keung To <kkto@csis.hku.hk>
Subject: Re: decision problems not in P
Date: 31 Oct 2000 16:43:10 +0800
Newsgroups: comp.theory,sci.math

>>>>> "David" == David Bernier <bernier@my-deja.com> writes:

    David> J. Hartmanis and R. Stearns: ``On the computational complexity of
    David> algorithms", Trans. Amer. Math. Soc., 117:285--306, 1965.

But why stop at Exponential time?  Consider the "simple" problem:

  Given two regular expressions over the alphabet {0, 1} allowing only
  concatenations, union, * and not.  Decide whether they are equivalent.

And then you know there are decision problems are not even elementary
(i.e. complexity worse than 2^2^2^...^2^n for any fixed number of "2^").
See STOC 93 pp. 1--9.

Regards,
Isaac.