Reachability problems in low-dimensional nondeterministic polynomial maps over integers

Ko, SK, Niskanen, R ORCID: 0000-0002-2210-1481 and Potapov, I (2021) Reachability problems in low-dimensional nondeterministic polynomial maps over integers. Information and Computation, 281. ISSN 0890-5401

Preview

Text Reachability problems in low-dimensional nondeterministic polynomial maps over integers.pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (530kB) | Preview

Abstract

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.

Item Type:	Article
Uncontrolled Keywords:	COMPLEXITY; Computer Science; Computer Science, Theory & Methods; Mathematics; Mathematics, Applied; MORTALITY; Physical Sciences; Science & Technology; SYSTEMS; Technology; TIME; UNDECIDABILITY BOUNDS; Science & Technology; Technology; Physical Sciences; Computer Science, Theory & Methods; Mathematics, Applied; Computer Science; Mathematics; UNDECIDABILITY BOUNDS; SYSTEMS; COMPLEXITY; MORTALITY; TIME; 08 Information and Computing Sciences; Computation Theory & Mathematics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions:	Computer Science and Mathematics
Publisher:	Elsevier
Date of acceptance:	23 June 2021
Date of first compliant Open Access:	9 January 2023
Date Deposited:	09 Jan 2023 13:21
Last Modified:	05 Jul 2025 11:00
DOI or ID number:	10.1016/j.ic.2021.104785
URI:	https://researchonline.ljmu.ac.uk/id/eprint/18574

View Item