Reconstructing numbers from pairwise function values

Abstract

The turnpike problem is one of the few "natural" problems that are neither known to be NP-complete nor solvable by efficient algorithms. We seek to study this problem in a more general setting. We consider the generalized problem which tries to resolve set A={a 1,a 2,⋯,a n } from pairwise function values {f(a i ,a j ) | 1≤i, j≤n} for a given bivariate function f. We call this problem the Number Reconstruction problem. Our results include efficient algorithms when f is monotone and non-trivial bounds on the number of solutions when f is the sum. We also generalize previous backtracking and algebraic algorithms for the turnpike problem such that they work for the family of anti-monotone functions and linear-decomposable functions. Finally, we propose an efficient algorithm for the string reconstruction problem, which is related to an approach to protein reconstruction. © 2009 Springer-Verlag Berlin Heidelberg.