The complexity of the isomorphism problem for computable projective planes

MaRDI QIDQ5398254zbMATH OpenFDO

Authors N. T. Kogabaev

Publication date 26 February 2014

zbMATH Keywords

computable modelDesarguesian projective planeisomorphism problemPappian projective planeprojective plane

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) General theory of linear incidence geometry and projective geometries (51A05)

Recommendations

• _1¹-completeness of the computable categoricity problem for projective planes
• The class of projective planes is noncomputable
• Noncomputability of classes of Pappian and Desarguesian projective planes
• Computable dimensions of Pappusian and Desarguesian projective planes
• The theory of projective planes is complete with respect to degree spectra and effective dimensions

Cited in

(14)

• Some algorithmic problems for projective planes
• On the complexity of polytope isomorphism problems
• _1¹-completeness of the computable categoricity problem for projective planes
• The embedding problem for computable projective planes
• scientific article; zbMATH DE number 4161543 (Why is no real title available?)
• Noncomputability of classes of Pappian and Desarguesian projective planes
• The class of projective planes is noncomputable
• scientific article; zbMATH DE number 6820278 (Why is no real title available?)
• On automaton presentations of projective planes
• The class of non-Desarguesian projective planes is Borel complete
• The isometry degree of a computable copy of ℓ p 1
• NP-Hardness of Computing PL Geometric Category in Dimension 2
• Computable dimensions of Pappusian and Desarguesian projective planes
• The \(\delta_\alpha^0\)-computable enumerations of the classes of projective planes

This page was built for publication: The complexity of the isomorphism problem for computable projective planes

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