On the Decidability of Finding a Positive ILP-Instance in a Regular Set of ILP-Instances - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

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

(1)
1
Petra Wolf
• Function : Author
• PersonId : 1059507

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).

Domains

Computer Science [cs]

Dates and versions

hal-02387299 , version 1 (29-11-2019)

Identifiers

• HAL Id : hal-02387299 , version 1
• DOI :

Cite

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⟩

28 View