6
$\begingroup$

Suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct. We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N − 1$), then we have a set $$A=\{a_1,a_2,...,a_{N-1} \}$$ As you know given $P$ and $N$, it is easy to build $A$. Although given $A$ and $K$ there could be many $P$'s leading to $A$ or even no possible $P$ leading to $A$.

I want to know, given $A$ and $K$, is there any algorithm just saying whether there is a $P$ leading to this $A$ or not?

$\endgroup$
7
$\begingroup$

Your problem seems a special case of the turnpike reconstruction problem (for which no polynomial time algorithm is known).

See for example: Shiteng Chen, Zhiyi Huang, and Sampath Kannan, "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)\mid 1 \leq i, j \leq 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....

$\endgroup$
  • 1
    $\begingroup$ Thank You for your help. But there is a little difference between turnpike problem and what i asked. The difference in my question is in modulus N, while in the references it is just the distance : $|p_i - p_j|$ $\endgroup$ – Mahdi Khosravi Jul 3 '13 at 18:28
1
$\begingroup$

"Beltway Reconstruction Problem” - arxiv.org/pdf/1212.2386.pdf may help. Note that you're asking for the function corresponding to $P$ whose autocorrelation is the given function corresponding to $A$.

I've often thought that there's some relation to factoring, at least to for the turnpike version.

You can consider $A$ as an integer $Z=a_1x^1+a_2x^2+⋯a_Nx^N$ in base $N$, and by factoring $Z$, some of those factors would be the indicator function of $P$, i.e. would be $1$ at the $k$'th position and $0$ otherwise. So maybe the turnpike problem is in $\mathsf{BQP}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.