Let K be a complexity class. We wish to recursively enumerate exactly those "graph languages" that can be decided in K. By graph languages, we mean languages whose inputs are graphs (say in adjacency matrix format) such that two isomorphic graphs are either both in the language or both not in the language. So, graph languages are "closed under isomorphisms". If this can be done for K, we say that the set of K graph properties is recursively indexable.
The set of NP graph properties is known to be recursively indexable. This is due to the fact that we have a logic for NP (i.e. existential second-order logic). On the other hand, it is a long-standing open problem whether P graph properties are recursively indexable. [No, you can't use the usual enumeration for clocked poly-time Turing machines as they contain "bad" graph languages.] Of course, the existence of a logic for P, which is another big open problem in finite model theory, will imply that P graph properties are recursively indexable. [(LFP+<)inv captures PTIME properties over ordered structures only.] Yuri Gurevich conjectured that P graph properties are not recursively indexable, and therefore, there is no logic for P. See his paper. In particular, if the conjecture is true, then P is different from NP as NP graph properties are recursively indexable! So, try to prove that P graph properties are not recursively indexable!
3 comments:
Can you talk a little more about what it means to have a logic on an ordered vs. an unordered structure? or point to a suitable reference?
David: sure. The next post will be on this issue. However, if you are impatient, just check out Graedel's tutorial on descriptive complexity, which you can find at http://www.cis.upenn.edu/~weinstein/fmta.html.
Alternatively, you may look at either Libkin's Element of Finite Model Theory book or Immerman's Descriptive Complexity book. [Look for the notion of a logic "capturing" a complexity class.]
Thanks for your considered reply!
Post a Comment