Re: Question on computational complexity

Artyom wrote:

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.

The construction I described encodes an arbitrary tally language into a set of graphs satisfying your uniformity condition. You can easily adapt it to encode languages over a binary alphabet and that will give you what you want. Here is one way you could do it.
Suppose you have a binary string w of length n. Define the graph G_w to consist of a disjoint union of cliques of different sizes. Specifically, it contains one clique of size k and in addition a clique of size k+i for each i such that the i-th bit of w is 1 and finally a clique of size k+n+1.

Now, for any language A of binary strings take the class of graphs S_A = {G_w | w in A}. There is an easy reduction from A to S_A. Moreover, S_A clearly has the property you wanted. So, if you start with A that is hard for the complexity class you want, so is S_A.

-Anuj.
.