Safety Problems are NP-complete for Flat Integer Programs with Octagonal Loops.

Marius Bozga Radu Iosif Filip Konecný

Published in: CoRR (2013)

Keyphrases

np complete
integer program
np complete problems
constraint satisfaction problems
satisfiability problem
np hard
conjunctive queries
randomly generated
pspace complete
computational complexity
linear program
decision problems
integer programming
mathematical programming
bounded treewidth