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

<p>See for example: Shiteng Chen, Zhiyi Huang, and Sampath Kannan, <a href="http://www.seas.upenn.edu/~hzhiyi/publications/CHK09-ISAAC.pdf">"Reconstructing Numbers from Pairwise Function Values"</a>. </p>

<p><strong>Abstract</strong>: 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 <em>Number Reconstruction
problem</em>. Our results include efficient algorithms when $f$
is monotone and non-trivial bounds on the number of solutions when $f$
is the sum....</p>

CC BY-SA 3.0
2013-07-03T18:28:27.923Z
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|$
Mahdi Khosravi
CC BY-SA 3.0
2013-07-02T20:58:15.247Z
2013-07-02T21:06:03.520Z
2013-07-02T21:06:03.520Z
Marzio De Biasi
<p>"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$.</p>

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

<p>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}$.</p>

CC BY-SA 3.0
2018-01-21T22:36:11.323Z
2018-01-21T22:36:11.323Z
Mark S
<p>Suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$
where $$1\leq p_k\leq N , k=1,...,K \qquad \&amp; \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$.</p>

<p>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?</p>

CC BY-SA 3.0
2013-07-09T08:34:07.553Z
[simultaneously cross-posted](http://mathoverflow.net/questions/135464/difference-sets) on MO.
Kaveh
<co.combinatorics><graph-algorithms><nt.number-theory><comp-number-theory><combinatorics>
Difference Sets
Mahdi Khosravi
# Difference Sets

(Asked by: username_0 on 2013-07-02)

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?

**Tags:** co.combinatorics, graph-algorithms, nt.number-theory, comp-number-theory, combinatorics

> **Comments:**
> **username_1**: [simultaneously cross-posted](http://mathoverflow.net/questions/135464/difference-sets) on MO.  

---

## 2 answers

### Answer by username_2 on 2013-07-02. Score: 7

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"](http://www.seas.upenn.edu/~hzhiyi/publications/CHK09-ISAAC.pdf).

**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....

> **Comments:**
> **username_0**: 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|$  

---

### Answer by username_3 on 2018-01-21. Score: 1

"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}$.


---

