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?

  • 4
    $\begingroup$ 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$. $\endgroup$ Mar 8, 2019 at 16:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.