Skip to Main content Skip to Navigation
Conference papers

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).
Document type :
Conference papers
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

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

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

55