Re: Question on computational complexity

Artyom wrote:
Thanks for reply, Anuj!

Maybe I have stated that desired condition somewhat vague, so I restate
it once more for clarity:
Can we find set of graphs S such that for any k there is N satisfying:
any two graphs from S 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?

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.

It seems to me that your statement of necessarily FO-definability of S
is wrong.
Take, for example, S to be cycle graphs C_n. Then S is obviously not
first-order definable, by playing for each fixed k on large enough
C_{2n} and 2*C_n. On the other hand, for each fixed k, C_n and C_m with
large enough m and n are indistinguishable as well.
So, it seems question is somewhat subtler.

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.

-Anuj.
.

Relevant Pages

  • Re: Indistinguishable families of graphs
    ... members are look-alikes. ... Can we find set of graphs S such that for any k there is N satisfying: ... undistinguashable by a k-round Ehrefeucht-Fraisse game? ...
    (sci.math)
  • Re: Question on computational complexity
    ... Maybe I have stated that desired condition somewhat vague, so I restate ... it once more for clarity: ... Can we find set of graphs S such that for any k there is N satisfying: ...
    (comp.theory)
  • Indistinguishable families of graphs
    ... members are look-alikes. ... Can we find set of graphs S such that for any k there is N satisfying: ...
    (sci.math)