Re: Question on computational complexity

Yes, I had assumed you also wanted the additional condition that any
graph that is indistinguishable from one in S is itself in S.
This would give the first-order definability I claimed.

Oh, yes, agree that stated.

But, in this case, you can construct such an S of any desired complexity
(even undecidable ones). In particular, take any set A of natural
numbers and consider the set of cycles S = { C_n | n in A }. S clearly
satisfies your condition but is at least as hard as A (considered as a
tally language). Since A is arbitrary, you get S of any desired complexity.

You are right, of course. What I actually wanted is to have such set
not only complex in itself, but also hard for some class in a sense of
existence of low-level reductions from all sets in that class to it.
What actually seems difficult to me is necessity to have simultaneously
high uniformity of members of S and some gadgets built in them which
we usually use constructing reductions. Probably such a construction
can be constructed straightforwardly, but I so far wasn't able to
figure out how.

Thank you again for comments,
Artyom

.