11
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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$
    – Emil Jeřábek
    Mar 8, 2019 at 16:37

0

Reset to default

Your Answer

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