# Computational Complexity of the Frobenius Problem

The Frobenius problem takes as input $$n$$ positive integers $$a_1,\ldots,a_n$$ with $$\gcd(a_1,\ldots,a_n)=1$$ and asks for the largest integer $$F$$ that cannot be written in the form $$F=a_1x_1+a_2x_2+\cdots+a_nx_n$$ with non-negative integers $$x_1,\ldots,x_n$$; this largest integer $$F$$ is the so-called Frobenius number $$F(a_1,\ldots,a_n)$$.

Jorge Ramirez Alfonsin (Complexity of the Frobenius problem. Combinatorica 16(1):143-147, 1996) has shown that it is NP-hard to determine the Frobenius number (under Turing reductions).

There is an unpublished manuscript by Shunichi Matsubara that seems to prove that the decision version of the Frobenius problem is $$\Sigma_2^p$$-complete under Karp reductions:

The computational complexity of the Frobenius problem, S Matsubara - arXiv preprint arXiv:1602.05657, 2016 - arxiv.org

The paper by Matsubara has only a single citation on google scholar, and this is from another paper by the same author. There is no conference version of the paper, and I also cannot find any journal version of this paper. The result (if correct) is important.

My question is: What's going on with this paper? Has it been verified? Does it perhaps contain a gap? Is it under submission to some journal? Or is the result already known?

• I have no answer to these questions. However, I observe that EXACTFROBENIUS is in $\Pi^P_2$, hence Conjecture 1 is false unless $\Sigma^P_2=\Pi^P_2$. – Emil Jeřábek supports Monica Mar 8 at 16:37