In descriptive complexity, HO corresponds to ELEMENTARY.

ELEMENTARY is a subset of R, so therefore all HO queries are decidable.

Then undecidable problems have no corresponding HO query. Is my understanding correct? If so, can I have an example undecidable problem and an intuitive/informal explanation of why it doesn't have a corresponding HO query?



Your Answer

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