Complexity of Finding Values of the Generalized Taxicab Number
Alexander Bolotin *
Department of Computer Science, Ben-Gurion University of the Negev, Beersheba, Israel.
*Author to whom correspondence should be addressed.
Abstract
This short paper demonstrates a sketch of a generic algorithm that can generate integers written as the sum of N mth positive powers with any N≥2 and m≥1 in two different ways. As it is shown in the paper, such a generic algorithm is NP-hard. One can infer from this result that to generate exact values of the generalized "Taxicab" (m,N,j)– the smallest sum of N mth positive powers expressed in j different ways – is at least as hard as the hardest problems in NP. This implies that except for small N to find the generalized "Taxicab " (m,N,j) would be unfeasible on any computing device.
Keywords: Generalized taxicab number, number partitioning problem, integer factorization, complexity, NP-hardness, NP-complete problems