Encountered this on sci.math
From: Robert Israel (israel.domain.name.hidden)
Subject: Re: are there problems that provably take exponential time to
solve?
Newsgroups: sci.math
Date: 2002-12-30 13:59:18 PST
Bennett Haselton <bennett.domain.name.hidden> wrote:
>Has it been proven that there are problems which are decidable, but
>cannot be solved in polynomial time?
Presburger arithmetic: the first-order theory of the natural numbers
with addition. See
<
http://www.wikipedia.org/wiki/Presburger+arithmetic>
Robert Israel israel.domain.name.hidden
Department of Mathematics
http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Received on Thu Jan 02 2003 - 23:11:11 PST