Re: Question on computational complexity

Artyom wrote:

3) Can we have in general a set of graphs(or any other structures as
well) hard for some complexity class not weaker than LOGSPACE such that
all its large enough members look quite similar. Some strict statement
of what "similar" means is here, for example:
http://groups-beta.google.com/group/sci.math/browse_thread/thread/9d100bc307771720

The condition on "similar" that you state in that thread:

> Can we find set of graphs S such that for any k there is N satisfying:
> any two graphs of order larger than N satisfy the same first-order
> formulas with at most k quantifiers, or equivalently are
> undistinguashable by a k-round Ehrefeucht-Fraisse game?

would imply that S is itself definable by a first-order formula
and therefore that S is in AC^0 and hence not hard for LOGSPACE
or higher classes.

So, the answer to your question is no.

-AD.
.