Descriptive complexity is a useful way to free yourself from computational considerations when studying complexity. One of those considerations is the encoding of the structures you are working on.

However, the way we usually see integers in descriptive complexity is exactly the same way we're used to with Turing machines : $n$ is an ordered set of $\log_2 n$ elements, together with a unary relation that is true on the $i$-th element iff the $i$-th bit is 1 in the binary representation of $n$. This means we see integers exactly as their encodings.

Moreover, one of the main questions in descriptive complexity is Chandra-Harel conjecture, i.e. is there a logic for P on unordered structures. As such, is there a way to see integers as unordered structure ? Such a way should still ensure that the encoding of an integer is (at least poly-)logarithmic in $n$.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.