On complexity of the existential and universal theories of finite fields

DOI10.17223/20710410/45/9MaRDI QIDQ5151279zbMATH OpenOpenAlexFDO

Authors Alexander Rybalov

Publication date 17 February 2021

Published in Prikladnaya Diskretnaya Matematika (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/pdm674

zbMATH Keywords

existential theoryfinite fieldsNP-hardnessuniversal theory

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Finite fields (field-theoretic aspects) (12E20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On generic complexity of the existential theories
• On the generic existential theory of finite graphs
• Computational complexity of sentences over fields
• scientific article; zbMATH DE number 4152523
• The complexity of linear problems in fields

Cites work

• Algebraic geometry over algebraic structures. III: Equationally Noetherian property and compactness
• The elementary theory of finite fields

Cited in

(4)

• On the generic existential theory of finite graphs
• Decidability of the restricted theories of a class of partial orders
• On generic complexity of the existential theories
• Computational complexity of sentences over fields

This page was built for publication: On complexity of the existential and universal theories of finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5151279)