On the Decidability of Finding a Positive ILP-Instance in a Regular Set of ILP-Instances

Abstract : The regular intersection emptiness problem for a decision problem P ($int_{\mathrm {Reg}}$(P)) is to decide whether a potentially infinite regular set of encoded P-instances contains a positive one. Since $int_{\mathrm {Reg}}$(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 $int_{\mathrm {Reg}}$-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 $int_{\mathrm {Reg}}$-problem for the well-known NP-complete problem Integer Linear Programming (ILP). It is shown that any DFA that describes a set of ILP-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 $int_{\mathrm {Reg}}$(ILP).
Keywords :
Document type :
Conference papers
Domain :

Cited literature [23 references]

https://hal.inria.fr/hal-02387299
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:36:10 PM
Last modification on : Friday, November 29, 2019 - 5:01:49 PM

File

Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Citation

Petra Wolf. On the Decidability of Finding a Positive ILP-Instance in a Regular Set of ILP-Instances. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.272-284, ⟨10.1007/978-3-030-23247-4_21⟩. ⟨hal-02387299⟩

Record views