Abstract: Пусть структура A лежит в некотором классе сложности K. Тогда $ n $-местное отношение R на A называется наследственно K-отношением, если в любой другой структуре B из К, изоморфной A, образ R относительно любого изоморфизма между A и B тоже лежит в классе K. В докладе будут рассмотрены некоторые вопросы, связанные с описанием отношений с таким свойством в структурах, вычислимых за полиномиальное время, и примитивно рекурсивных структурах, в первую очередь в полях.

Cite: Алаев П.Е.
Наследственно алгоритмические отношения в структурах
IV Конференция математических центров России, посвященная 300-летию СПбГУ и РАН. 06-11 авг. 2024