Re: examples of EXPTIME

From: d. lee (scikid_at_gmail.com)
Date: 10/06/04 

Date: 6 Oct 2004 09:31:42 -0700

Many thanks for all answers.

My aim was to understand examples and their proofs of "not in P"
problems.
I buyed the book of papadimitriou and have read some other books about
complexity theory
(such as Sipser). But still don't know a single proof example of "not
in P" -_-.

My remaining questions are

1. Is there a simple example of "not in P" proof in any problem?
   (I know Razborov's restricted arguments on circuit complexity)

2. Exp-complete means automatically "not in P" by time hierachy
theorem?

3. Could you explain what are the CVAL and succinct CVAL problems?