2
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.