Abstract: We consider some questions related to the problem of searching a structure A computable in polynomial time (in short, P-computable), which is isomorphic to a given abstract structure B. In particular, a general criterion for the existence of such a P-computable structure B is formulated. As an application, we discuss some questions about the existence of P-computable presentations for a series of classical objects, including fields and Abelian groups.

Cite: Alaev P.
Search of structures computable in polynomial time
Discrete and Continuous Signals: Analysis, Information and Applications, Международная конференция, 11-16 декабря 2023, Санкт-Петербург 11-16 Dec 2023