Reachability problems in low-dimensional nondeterministic polynomial maps over integers

S. K. Ko, R. Niskanen, I. Potapov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We study reachability problems for various nondeterministic polynomial maps in Zn. We prove that the reachability problem for very simple three-dimensional affine maps (with independent variables) is undecidable and is PSPACE-hard for both two-dimensional affine maps and one-dimensional quadratic maps. Then we show that the complexity of the reachability problem for maps without functions of the form ±x+a0 is lower. In this case the reachability problem is PSPACE for any dimension and if the dimension is not fixed, then the problem is PSPACE-complete. Finally we extend the model by considering maps as language acceptors and prove that the universality problem is undecidable for two-dimensional affine maps.

Original languageEnglish
Article number104785
JournalInformation and Computation
StatePublished - Dec 2021


Dive into the research topics of 'Reachability problems in low-dimensional nondeterministic polynomial maps over integers'. Together they form a unique fingerprint.

Cite this