Mathematics and Statistics Seminars
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
Title: The Complexity of Solution-free Sets of Integers
Abstract: Given a linear equation L, a set A of integers is L-free if A does not contain any
non-trivial solutions to L. We show that for any linear equation L with at least three variables, it is NP-complete to decide if a given set of integers contains a solution-free subset of a given size, and that the problem remains hard for sets of integers whose elements are polynomially bounded in the size of the set. We also consider the problem of counting the number of solution-free subsets ofa given set, and show that this problem is #P-complete for any linear equation in
at least three variables.
This is joint work with Keith Edwards.
Contact name:
Swati Chandna