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

Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2

Reply via email to