On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
Petra Wolf · Acta Informatica · 2022
Abstract The regular intersection emptiness problem for a decision problemP( $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg (P)) is to decide whether a potentially infinite regular set of encodedP-instances contains a positive one. Since $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg (P) is decidable for some NP-complete problems and undecidable for others, its investigation provides insights in the nature of NP-complete problems. Moreover, the decidability of the $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg -problem is usually achieved by exploiting the regularity of the set of instances; thus, it also establishes a connection to formal language and automata theory. We consider the $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg -problem for the well-known NP-complete problemInteger Linear Programming(ILP). It is shown that any DFA that describes a set ofILP-instances (in a natural encoding) can be reduced to a finite core of instances that contains a positive one if and only if the original set of instances did. This result yields the decidability of $${{\textit{int}}_{{\mathrm {Reg}}}}$$ intReg (ILP).