*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