Encountered this on sci.math
From: Robert Israel ([EMAIL PROTECTED])
Subject: Re: are there problems that provably take exponential time to solve?
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
Robert Israel [EMAIL PROTECTED]
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2