On the complexity of Diophantine geometry in low dimensions Conference Paper uri icon


  • The average-case complexity of some otherwise undecidable or open Diophantine problems is addressed. In particular, the possibility of solving some problems within PSPACE is demonstrated. A practical point of interest is that the considered Diophantine problems should perhaps be avoided in the construction of crypto-systems.

published proceedings

  • Proceedings of the Annual IEEE Conference on Computational Complexity

author list (cited authors)

  • Rojas, J. M.

complete list of authors

  • Rojas, JM

publication date

  • January 1999