-3
$\begingroup$

I learned about ASM recently and was interested how it could used for descriptive complexity theory.

Such link seems natural to me: you can give construction of algebraic model for formula as an ASM. Refining ASM further you get regular machine and prove complexity bound for it.

Is this possible to prove core description complexity theorems this way? Are there a reference for this? I did not found any.

Improve this question
$\endgroup$
4
  • $\begingroup$ SE did not sent last sentence. Fixed this. So hopefully closing cast for clarity is not standing anymore. If not, please articulate your position. $\endgroup$
    – uhbif19
    Nov 8 at 8:41
  • $\begingroup$ Your question is not clear, for instance what do you mean by an "algebraic model of a formula"? What is more, your first sentence speaks about "descriptive complexity" while the last one refers to "description complexity". These are two different things. Which you do you have in mind? $\endgroup$
    – Bartosz Bednarczyk
    Nov 9 at 8:19
  • $\begingroup$ "Which you do you have in mind?" I mean the link between FMT and complexity theory. The one which is in Fagin theorem or Neil Immerman "Descriptive Complexity" book. $\endgroup$
    – uhbif19
    Nov 10 at 9:14
  • $\begingroup$ > what do you mean by an "algebraic model of a formula" Well, that is kinda the point of this question, how would you construct such an "algebraic model" and if it is possible at all. If I know exactly how to do it, then why would I need to ask? As I see it you might have "empty" structure as the first step of ASM and add "fresh" variables trying to conform to the formula at each step. That seems like an algoritmisation of constructing some syntactic "free" model to me. $\endgroup$
    – uhbif19
    Nov 10 at 9:17

1 Answer 1

Reset to default
0
$\begingroup$

Found one clear link: work on Choiceless PTime characterization with ASM. The introduction section explains that encoding to string is required for the Turing machines model, so ASM may be an alternative lifting need of such encoding.

At the same time seems like more recent articles about Choiceless PTime do use/extend CPT logic from the first paper, but do not mention its relation to ASM.

Improve this answer
$\endgroup$

Your Answer

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