Encountered this on sci.math
From: Robert Israel ([EMAIL PROTECTED])
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 <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED]
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
