2016/02/18 by Shunichi Matsubara, Matsubara, Shunichi
Computer Science · Mathematics · #Coding theory and cryptography #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Polynomial and algebraic computation #cs.CC
paper · pdf · doi:10.48550/arxiv.1602.05657
openalex publication_date 2016/02/18 · arxiv created 2016/11/15 · arxiv updated 2016/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, as a main theorem, we prove that the decision version of the Frobenius problem is Sigma2P-complete under Karp reductions.Given a finite set A of coprime positive integers, we call the greatest integer that cannot be represented as a nonnegative integer combination of A the Frobenius number, and we denote it as g(A). We call a problem of finding g(A) for a given A the Frobenius problem; moreover, we call a problem of determining whether g(A) >= k for a given pair (A, k) the decision version of the Frobenius problem, where A is a finite set of coprime positive integers and k is a positive integer. For the proof, we construct two Karp reductions. First, we reduce a 2-alternating version of the 3-dimensional matching problem, which is known to be Pi2P-complete, to a 2-alternating version of the integer knapsack problem. Then, we reduce the variant of the integer knapsack problem to the complement of the decision version of the Frobenius problem. As a corollary, we obtain the main theorem.