  In this paper, as a main theorem, we prove that the decision version of the
Frobenius problem is Sigma_2^P-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
Pi_2^P-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.
