Skip to main content

Mathematics and Statistics Seminars

Venue: Birkbeck Main Building, MAL 745

This event has ended.

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: