Resolution of the Frobenius Problem with an Adiabatic Quantum Computer

Resolution of the Frobenius Problem with an Adiabatic Quantum Computer J. Ossorio-Castillo1(B)and Jos´e M. Tornero2 1Departamento de ´ Algebra, Universidad de Sevilla, 41012 Sevilla, Spain [email protected] 2Departamento de ´ Algebra – IMUS, Universidad de Sevilla, 41012 Sevilla, Spain [email protected] Abstract. The (Diophantine) Frobenius problem is a well-known NPhard problem (also called the stamp problem or the chicken nugget problem) whose origins lie in the realm of combinatorial number theory. In this paper we present an algorithm which solves it, via a translation into a QUBO problem of the so-called Ap´ery set of a numerical semigroup. This algorithm was specifically designed to run in an adiabatic quantum computer (a D-Wave 2X machine), and the performance problems for this precise setting are also discussed. Keywords: Quantum computation ·Adiabatic quantum computation ·Numerical semigroups ·Frobenius problem 1 Numerical Semigroups and the Frobenius Problem The study of numerical semigroups has its origins at the end of the 19th Century, when James Joseph Sylvester (1814–1897) and Ferdinand Georg Frobenius (1849–1917) were both interested in what is now known as the Frobenius problem, which we proceed to enunciate. Definition 1. Let a1,a 2,...,a n∈Z≥0with gcd(a1,a 2,...,a n)=1, the Frobenius problem, or FP, is the problem of finding the largest positive integer that cannot be expressed as an integer conical combination of these numbers, i.e., as asum n  i=1 λiaiwith λi∈Z≥0. This problem, so easy to state, can be extremely complicated to solve in the majority of cases, as will be seen later. It can be found in a wide variety of contexts, being the most famous the problem of finding the largest amount of money which cannot be obtained with a certain set of coins: if, for example, we have an unlimited amount of coins of 2 and 5 units, we can represent any quantity except 1 and 3. c The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 K. Arai (Ed.): Intelligent Computing, LNNS 283, pp. 292–310, 2022. https://doi.org/10.1007/978-3-030-80119-9_16 Resolution of the Frobenius Problem with an Adiabatic Quantum Computer 293 In order to understand the relationship between this problem and numerical semigroups, we shall first define the latter. Definition 2. A semigroup is a pair (S, +),whereSis a set and +is a binary operation +:S×S→Sthat is associative. Definition 3. A numerical semigroup Sis a subset of the non-negative integers Z≥0which is closed under addition, contains the identity element 0, and has a finite complement in Z≥0. From now on, we shall denote numerical semigroups as S, taking for granted that they are commutative and that their associated operation is the addition. As it can be easily noted, a numerical semigroup is trivially a semigroup. In other words, a numerical semigroup is a semigroup that, additionally, is a monoid (i.e., it also has an identity element) and has finite complement in Z≥0. In order to work with numerical semigroups, it will be necessary to characterize them somehow. For that let us set forth the following lemma. The proof of this result (and of any other result in this section, unless otherwise stated) can be found in [24]. Lemma 4. Let A={a1, ..., an}be a nonempty subset of Z≥0.Then, S=A=a1, ..., an={λ1a1+... +λnan|λi∈Z≥0} is a numerical semigroup if and only if gcd(a1, ..., an)=1. The previous lemma tells us that, drawing from a finite set A⊆Z≥0,itis possible to generate a semigroup S=Aas long as the elements of Asatisfy a certain condition. In this context, any set Asuch that S=Afor a certain numerical semigroup Sis called a system of generators of S. Even more, it can be proved that any numerical semigroup can be expressed that way, as will be shown next. Theorem 5. Every numerical semigroup Sadmits a unique minimal system of generators, which can be calculated as S∗\(S∗+S∗)with S∗=S\{0}. Corollary 6. Let Sbe a numerical semigroup generated by A={a1,...,a n} with 0=a1<a 2< ... < an.Then,Ais a minimal system of generators of Sif and only if ai+1 /∈a1,a 2,...,a i, for all i∈{1,...,n−1}. It will be stated later in this section that the minimal system of generators of a numerical semigroup is in fact finite. Hereinafter, if we say that S=Awith A={a1,a 2,...,a n}is a numerical semigroup, then we shall assume without loss of generality that a1<a 2<···<a n, gcd(a1,a 2,...,a n) = 1, and that Ais the minimal system of generators of S. Some examples of numerical semigroups, which will be used for the rest of the section, are: 3,7={0,3,6,7,9,10,12,→}, 4,9={0,4,8,9,12,13,16,17,18,20,21,22,24,→}, 5,8,11={0,5,8,10,11,13,15,16,18,→}, 5,7,9={0,5,7,9,10,12,14,→}, 294 J. Ossorio-Castillo and J. M. Tornero where →means that all integers thenceforth are also included in the numerical semigroup. Having thus defined and characterized what numerical semigroups are, we proceed to describe some of their combinatorial invariants. Definition 7. Let S=a1,a 2,...,a nbe a numerical semigroup, then m(S)=a1and e(S)=n are called respectively the multiplicity of Sand the embedding dimension of S. Lemma 8. Let Sbe a numerical semigroup, then m(S) = min S∗ Definition 9. The set of gaps of a numerical semigroup Sis defined as G(S)=Z≥0\S. Its cardinal, g(S)=|G(S)|, is called the genus of S; and its maximum, f(S) = max G(S), is called the Frobenius number of S. In other words, as by definition any numerical semigroup Shas a finite complement in Z≥0, we can define the maximum of such complement as f(S), known as the Frobenius number. In fact, the Frobenius problem described at the beginning of this chapter in Definition 1can be enunciated as the problem of finding f(S) for a certain numerical semigroup S. We shall expand the concepts related to the difficulties that surround the calculation of the Frobenius number later on. Table 1shows the combinatorial invariants associated for the previously given examples of semigroups. Table 1. Combinatorial invariants for some examples of semigroups S=Am(S)e(S)G(S)g(S)f(S) 3,73 2 {1,2,4,5,8,11}6 11 4,94 2 {1,2,3,5,6,7,10,11,14,15,19,23}12 23 5,8,115 3 {1,2,3,4,6,7,9,12,14,17}10 17 5,7,95 3 {1,2,3,4,6,8,11,13}8 13 Roger Ap´ery (1916–1994), better known for proving in 1979 the irrationality of ζ(3) [2], also laid the background in the context of the resolution of singularities of curves [1] for an important set associated to a numerical semigroup S and one of its elements. Resolution of the Frobenius Problem with an Adiabatic Quantum Computer 295 Definition 10. The Ap´ery set of a numerical semigroup Swith respect to a certain s∈S∗is defined as Ap(S, s)={x∈S|x−s/∈S}. A possible characterization of the elements of the Ap´ery set one by one, which will come to special use in the third section, is given by the following lemma. Lemma 11. Let Sbe a numerical semigroup and let s∈S∗.Then,Ap(S, s)= {ω0,ω 1, ..., ωs−1}where ωiis the least element of Scongruent with imodulo s, for all i∈{0, ..., s −1}. Consequently, |Ap(S, s)|=s. By means of an example on how to calculate the Ap´ery set of a semigroup with respect to a certain element, let S=5,8,11={0,5,8,10,11,13,15,16,18,→}. Then Ap(S, 5) = {ω0,...,ω 4}, where ω0= min{x∈S|x≡0mod5}=0 ω1= min{x∈S|x≡1mod5}=11 ω2= min{x∈S|x≡2mod5}=22 ω3= min{x∈S|x≡3mod5}=8 ω4= min{x∈S|x≡4mod5}=19 We proceed to hint how the Ap´ery set proves some elementary (but nevertheless important) results of numerical semigroups. Proposition 12. The minimal system of generators of a numerical semigroup Sis finite. Proof. Let s∈S∗. Then, it is easy to see that for every t∈Sthere exists a unique pair (u, v)∈Z≥0×Ap(S, s) such that t=us+v.Thus,Sis generated by A=Ap(S, s)∪{s}and, as Ais finite, the unique minimal system of generators must be finite. Lemma 13. Let Sbe a numerical semigroup, then e(S)≤m(S). Proof. Let a=m(S) and let A=Ap(S, a)∪{a}.Thus,asScan be generated by A\{0}and |A\{0}| =a, we can conclude that e(S)≤m(S). The Ap´ery set is noteworthy in the context of the Frobenius problem as there exists a relationship between its members (regardless of the element s∈S∗we choose) and the Frobenius number, which we proceed to enunciate. 296 J. Ossorio-Castillo and J. M. Tornero Theorem 14 (A. Brauer – J. E. Shockley, 1962) [7].Let Sbe a numerical semigroup and let s∈S∗.Then f(S) = max Ap(S, s)−s g(S)=1 s⎛ ⎝ ω∈Ap(S,s) ω⎞ ⎠−s−1 2 Now we exemplify the relationship between numerical semigroups and combinatorial optimization, as one of the most important problems in the latter branch of mathematics, known as the knapsack problem or rucksack problem, and more concretely one of its variants [21] (p. 374), can be seen as the problem of deciding if a given integer tbelongs to a certain numerical semigroup S. Definition 15. The numerical semigroup membership problem, or NSMP,is the problem of determining if, given a certain integer t∈Z≥0and a numerical semigroup S=a1, ..., an, the integer tis contained in S. That is to say, if there exist non-negative integers λ1,...,λ n∈Z≥0such that n  i=1 λiai=t. The numerical semigroup membership problem is in NP-complete,asshown in [21]. This fact was used by Jorge Ram´ırez-Alfons´ın in 1996 [22] to finally prove that the Frobenius problem is in NP-hard (under Turing reductions). For that, he defined a polynomial algorithm ΛNSMP for solving the NSMP which uses as a subroutine an unknown algorithm ΛFP that solves the Frobenius problem. Thus, he proved that the NSMP can be Turing reduced to the FP. As the NSMP is in NP-complete, he concluded that the FP is in NP-hard. 2 The Ising Spin Problem in Adiabatic Quantum Computing Our tackle of the Frobenius problem uses adiabatic quantum computing, more specifically that related to the Ising spin problem. This problem has a story where NP-hard problems are no strangers. A form of adiabatic quantum computation [19] is quantum annealing, where a known initial configuration of a quantum system evolves towards the ground state of a Hamiltonian that encodes the solution of an NP-hard optimization problem. The Canadian company D-Wave Systems announced in 2011 the first commercially available quantum annealer, composed of arrays of eight superconducting flux quantum bits with programmable spin–spin couplings, and published their results [18]. Subsequently in 2013, S. Boixo et al. [4] published their experimental results on the 108-qubit D-Wave One device. Their last chip (by the date of this work), released in 2017 and called D-Wave 2000Q, has 2,048 Resolution of the Frobenius Problem with an Adiabatic Quantum Computer 297 qubits in a Chimera graph architecture [11], and can be seen as a computer that solves the Ising spin problem, a particular type of quantum annealing which we proceed to describe. The Ising spin model, originally formulated by Wilhelm Lenz and first solved by his student, Ernst Ising [17], consists of a model of ferromagnetism in statistical mechanics in which we have to find the ground state of a system of n interacting spins. If we represent the spins of these particles as binary variables si∈{−1,1}with i∈{1,...,n}, then the Ising Spin problem can be expressed as an integer optimization problem whose objective is to find the spin configuration of the system that minimizes the function H(s1,...,s n)= n  i=1 hisi+ n−1  i=1 n  j=i+1 Jijsisj, where hi∈Ris the energy bias acting on particle i(i.e. the external forces applied to each of the individual particles) and Jij ∈Ris the coupling energy between the spins iand j(i.e. the interaction forces between adjacent spins). This problem was proved to be in NP-hard by Francisco Barahona [3], and can be effectively solved with the hardware implemented by D-Wave, whose chip permits to program independently the values of hiand Jij [4,18]. It will be shown in the next section how to embed a certain optimization problem inside the D-Wave machine. 3 Resolution of the Frobenius Problem with an Adiabatic Quantum Computer The next algorithm shows the possibilities of calculating the Ap´ery set and the Frobenius number of a numerical semigroup with an actual adiabatic quantum computer. As described in the previous section, current D-Wave quantum annealers solve a certain kind of mathematical optimization problems known as Ising spin problems, namely H(s1,...,s n)= n  i=1 hisi+ n−1  i=1 n  j=i+1 Jijsisj with si∈{−1,1}, where the objective is to find the minimum of H(s1,...,s n). On the other hand, we recall that the Ap´ery set with respect to s∈S\{0}, where S=a1,...,a nis a numerical semigroup, is defined as Ap(S, s)={x∈S|x−s/∈S}. The question is, how could we be able to translate the problem of computing Ap(S, s) to the Ising spin model solved by the D-Wave machine? We have already shown in Lemma 11 that Ap(S, s)={ω0,...,ω n−1}, where ωi= min{x∈S:x≡imod s}. 298 J. Ossorio-Castillo and J. M. Tornero How about transforming the definition of ωiinto the answer of a mathematical optimization problem? Definition 16 [21].An integer linear program, or ILP, is defined in its canonical form as the optimization problem: min cTx subject to: Ax =b where x∈Zn ≥0,A∈Zn×Zm,b∈Zmand c∈Zn. Thus, it is straightforward to see that the calculation of each of the ωican be redefined as the following ILP: min n  j=1 ajxj subject to: n  j=1 ajxj=i+sk, with xj∈Z≥0for all j=1, ..., n and k∈Z≥0. This mathematical optimization problem represents a way of calculating the Ap´ery set in its own right and, although integer linear programming is in NPhard and its recognition version (deciding whether Ax =bhas a feasible solution or not regardless of its optimality) is in NP-complete [21], this computational complexity arises in the general case. In our context, it may prove to be an easier problem; however, details on this remain to be worked out. This approach for the calculation of the Ap´ery set first appeared in [15], although Greenberg’s work dealt with the direct calculation of the Frobenius number by means of Ap(S, a1), as will be discussed later. We have tested this algorithm using state-of-the-art optimization software for integer optimization. In our case, the optimization problem for ωiwas modeled using AMPL [12,13], an algebraic modeling language for solving mathematical optimization problems. AMPL has a clear advantage, as our problem is entirely parameterized and AMPL allows us to describe the generic problem in a .mod file while defining the actual values for the parameters in a separate .dat file. This way, we have just to change the parameters inside the .dat file in order to solve a new instance of the Ap´ery set. The .mod fileweproposeisshownin Fig. 1(the names of the parameters and variables of the problem are maintained so that no further explanation is required). Let us suppose that we are interested in the numerical semigroup S= 11,19,23, and that we want to calculate the Ap´ery set of s= 30 (i.e., Ap(S, 30)). The calculation of, for example, ω5∈Ap(S, 30), will have the associated .dat file depicted in Fig. 2. In order to compute ω5, we also need a .run file that will load the model and the data of the problem, and which will also call the solver for solving the problem. In our case, the solver we have chosen is Gurobi [16] which, among other things, solves integer linear problems. The .run Resolution of the Frobenius Problem with an Adiabatic Quantum Computer 299 file we have used is shown in Fig. 3, and the corresponding output we obtain can be seen in Fig. 4. This output tells us that ω5= 65 and also that a representation of 65 with respect to the generators of the semigroup is 65 = 0 ×(11) + 1 ×(19) + 2 ×(23). We can also write an alternative .run file that will directly calculate and display the whole content of the Ap´ery set for a certain s∈S.First,wehavetodrop the param i := 5; line from the .run file, as it will be changed in each iteration of the main loop, and modify the .run so that it will look like the one in Fig. 5. Thus, we obtain Ap(S, 30) = {0,11,19,22,23,33,34,38,42,44,45,46,55,56, 57,61,65,66,67,69,77,78,80,84,88,89,92,100,103,111}(see Fig. 6for the actual output). Fig. 1. File apery set member.mod Fig. 2. File numerical semigroup.dat This algorithm also provides a way for calculating the Frobenius number of a numerical semigroup. We recall that, for any numerical semigroup Sand any integer s∈S\{0}, then f(S) = max {Ap(S, s)}−s. 300 J. Ossorio-Castillo and J. M. Tornero Thus, as the difficulty of obtaining f(S) this way increments with respect to the number swe choose (we have to solve sILPs), the smartest way of proceeding is by solving it in the case where s= min(S\{0}) (i.e., s=a1,asdoneby[15]). The AMPL file that represents this approach is shown in Fig. 7. In our case, the output (Fig. 8) tells us that f(S) = 81. All these files can be found in the public GitHub repository [20]; however, a license for both AMPL and Gurobi is needed in order to run them and obtain the same results (or any result at all). What we have shown is a classical algorithm for obtaining the Ap´ery set and the Frobenius number in a general manner that depends on a black box that solves an ILP with global optimality. From now on we will explain the steps we have followed in order to solve this ILP with an adiabatic quantum computer and, specifically, with a D-Wave 2X machine (and also the obstacles we have encountered in that path). In order to transform this ILP problem into the Ising model solved by the D-Wave hardware, one step further involves changing its integer variables into a new set of binary variables with at most a polynomial cost. Definition 17 [21].A binary linear program, or BLP, is defined in its canonical form as: min cTx subject to: Ax =b where x∈{0,1}n,A∈Zn×Zm,b∈Zmand c∈Zn. Both problems are polynomially equivalent, as shown in [21] (Theorem 13.6), where an upper bound for the number of binary variables representing each integer variable from the original ILP problem is given. However, we can tight this number of binary variables by using our knowledge of the problem and one of the lower bounds of the Frobenius number given in [23] (ideally, we could use f(S)). In 1935, Issai Schur proved in a lecture in Berlin [6,23] the following result: Fig. 3. File apery set member.run Resolution of the Frobenius Problem with an Adiabatic Quantum Computer 307 Right now, an ideal quantum annealer should be able to solve our QUBO problem for finding the members of the Ap´ery set, provided that such a computer has a sufficiently large enough amount of qubits, and also that the graph connecting the qubits is complete. However, to date there are no quantum annealers that fulfill those requirements (they may be available in the future, though). The latest quantum annealers commercially available are the D-Wave 2X, with 1152 and 3360 couplers (connections between adjacent qubits), and the D-Wave 2000Q, which has 2048 qubits and 6016 couplers. Their graphs are far from being complete, as every qubit in their grids are at most connected with six other qubits, as shown in Fig. 15 (it may be less than that, as some qubits may be off after the last recalibration of the machine). The importance of the completeness of the graph is problem dependent. Our QUBO instance, for example, has a complete connectivity graph between its variables. With an ideal quantum annealer we would have no problem, but with the D-Wave machine it is mandatory to transform our problem graph into an alternative graph that could be embedded into the Chimera graph. In other words, we have to solve an instance of the subgraph isomorphism problem, which happens to be in NP-complete. Even more, our problem may not be embeddable inside the D-Wave (for example, for the 1152 qubit Chimera grid of the D-Wave 2X, the largest complete graph that can be embedded into it is believed to be the K33). Research on the subject of embedding a problem graph into D-Wave’s Chimera graph can be found in [8] and [9], where the concepts of embedding and parameter setting are explained. There is a way to skip these limitations, by solving subinstances of our graph instead of the complete graph. For that, D-Wave released a graph partitioning open source library called qbsolv [5]. Its corresponding executable needs a Fig. 13. Example of .qubo file Fig. 14. Output for the example .qubo file 308 J. Ossorio-Castillo and J. M. Tornero Fig. 15. Introducing a problem inside the D-Wave 2X certain kind of file format (called .qubo), to work. For example, if our QUBO instance is defined by 2.6x0+4.5x1−1.8x2+3.5x0x1+2x1x2, where x0,x 1,x 2∈{0,1},its corresponding .qubo file is the one shown in Fig. 13. The format is quite: the first line always starts with p qubo 0, followed by the number of variables, the number of nonzero diagonals, and the number of nonzero couplings. The output obtained by qbsolv for this file can be seen in Fig. 14. Please note that, in the previous paragraph, we have shown the solution that qbsolv obtains for a certain instance of the problem. This is because qbsolv has an auxiliary internal optimization solver based on the tabu search [14], which gives a solution for the subproblems and then unifies all the solutions into the complete one for all the variables. However, this classical method does not guarantee a global solution, and is of no help to us in the general case. We can decide if qbsolv tries to solve the problem with its tabu search, of if we prefer to connect to a D-Wave machine. Finally, our QUBO subproblem is solved with the D-Wave 2X via one of the possible inputs allowed. The first one is shown in Fig. 15, while the second one is again a .qubo file obtained internally with qbsolv. As part of the project Resolution of the Frobenius Problem with an Adiabatic Quantum Computer 309 Joint Research Unit Repsol-ITMATI (code file: IN853A 2014/03), we had the opportunity to try the D-Wave 2X machine based on the University of Southern California. However, due to the amount of subproblems needed to solve a proper instance of the Frobenius problem or the Ap´ery set, it was impractical to do so with the amount of time given and the current size of the graph of the D-Wave 2X machine. 4 A Word on Conclusions Regarding the algorithms for the Ap´ery set and the Frobenius number, there are two aspects that need to be improved prior to completing a study of its feasibility and performance. First, the current graph (i.e., Chimera graph) architecture of the available adiabatic quantum computers (i.e., the D-Wave machines) extremely obstruct the resolution of problems that have an almost full connectivity index between its variables, as in this case (the use of qbsolv is just a temporary workaround, or it should be as so). And second, current adiabatic quantum computers do not guarantee global optimality, as opposed to the theoretical result deducted from the adiabatic theorem; in reality, the D-Wave just make a few runs of the process (instead of just one, as would be in the theoretical case) and, following a certain probability distribution, try to guarantee that the best of the solutions obtained by those runs is in fact the global solution to the problem. This solution, however, cannot be proven to be the global optimum (as global optimality is not known to be in the class NP), which makes useless our attempt to find those two combinatorial invariants via current adiabatic quantum computers. In the future, with more reliable quantum annealers, however, this solution may prove to be effective and faster, but for now it is just a theoretical method. References 1. Ap´ery, R.: Sur les branches superlin´eaires des courbes alg´ebriques. C. R. Acad. Sci. Paris 222, 1198–1200 (1946) 2. Ap´ery, R.: Irrationalit´edeζ(2) et ζ(3). In: Luminy Conference on Arithmetic. Ast´erisque, vol. 61, pp. 11–13 (1979) 3. Barahona, F.: On the computational complexity of Ising spin glass models. J. Phys. A: Math. Gen. 15(10), 32–41 (1982) 4. Boixo, S., et al.: Quantum annealing with more than one hundred qubits. arXiv preprint arXiv:1304.4595 (2013) 5. Boot, M., Reinhardt, S., Roy, A.: Partitioning optimization problems for hybrid classical/quantum execution. Technical report, D-Wave Systems, Inc. (2017) 6. Brauer, A.: On a problem of partitions. Am. J. Math. 64, 299–312 (1942) 7. Brauer, A., Shockley, J.E.: On a problem of Frobenius. J. Reine Angew. Math. 211, 215–220 (1962) 8. Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7(5), 193–209 (2008) 310 J. Ossorio-Castillo and J. M. Tornero 9. Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10(3), 343–353 (2011) 10. D-Wave Systems Inc: D-Wave: Programming with QUBOs. Release 1.5.1-beta4, 09-1002A-B (2016) 11. D-Wave Systems Inc: D-Wave: Programming with QUBOs. Release 2.3, 09-1002AB (2016) 12. Fourer, R., Gay, D.M., Kernighan, B.W.: A modeling language for mathematical programming. Manag. Sci. 36(5), 519–554 (1990) 13. Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. Duxbury Press (2002) 14. Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986) 15. Greenberg, H.: An algorithm for a linear Diophantine equation and a problem of Frobenius. Numer. Math. 34(4), 349–352 (1980) 16. Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2018). http:// www.gurobi.com. Accessed 23 Feb 2019 17. Ising, E.: Report on the theory of ferromagnetism. Z. Phys. 31, 253–258 (1925) 18. Johnson, M.W., et al.: Quantum annealing with manufactured spins. Nature 473(7346), 194 (2011) 19. McGeoch, C.C.: Adiabatic quantum computation and quantum annealing: theory and practice. Synth. Lect. Quantum Comput. 5(2), 1–93 (2014) 20. Ossorio-Castillo, J.: jqnoc/numsem: numsem console (2018). https://doi.org/10. 5281/zenodo.1257967 21. Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Courier Corporation (1998) 22. Ram´ırez-Alfons´ın, J.L.: Complexity of the Frobenius problem. Combinatorica 16(1), 143–147 (1996) 23. Ram´ırez-Alfons´ın, J.L.: The Diophantine Frobenius problem. Oxford University Press, Oxford (2005) 24. Rosales, J.C., Garc´ıa-S´anchez, P.A.: Numerical Semigroups. Springer, New York (2009). https://doi.org/10.1007/978-1-4419-0160-6