associated equivalence relation R

L

has finitely many equivalence classes.

defined by

def

= {*wc*

|w|

rev

:* w* ∈ {*a,b*}

*

}.

If *T* is a deterministic Turing machine with *q* states that recognizes *L*,

then for each integer *n* ≥ log

2

that on input *w* the machine *T* executes at least *n*

2

/log *q* steps before

halting.

of n variables have circuit complexity greater than (1 − *ϵ*)2

/*n*.

NSPACE(*f*(*n*)) ⊆ SPACE(*f*(*n*)

2

)

P

A

= NP

A

P

B

≠ NP

B