Can you identify the sum of two permutations in polynomial time? There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question:

Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ numbers such that $\sum_{i=1}^n a_i = n(n+1).$  Decompose it into the sum of two permutations, $\pi$ and $\sigma$, of $1 \dots n$, so that $a_i = \pi_i + \sigma_i\,$.

There are some necessary conditions: if the $a_i$  are sorted so that $a_1 \leq a_2 \leq \ldots \leq a_n\,$, then we must have

$$\sum_{i=1}^k a_i \geq k(k+1).$$

However, these conditions are not sufficient. From the answer to this math.se question I asked, the sequence 5,5,5,9,9,9 cannot be decomposed as the sum of two permutations (one can see this by using the fact that both 1 or 5 can only be paired with 4). 

So my question is: what is the complexity of this problem?
No, you can not identify the sum of two permutations in polynomial time unless P=NP. Your problem is NP-complete since the decision version of your problem is equivalent to the NP-complete problem $2$-Numerical Matching with target sums:

Input: Sequence of $a_1, a_2, \ldots a_n$ of positive integers, $\sum_{i=1}^n a_i = n(n+1)$, $1 \le a_i \le 2n$ for $1 \le i \le n$

Question: Are there two permutations $\psi_1$ and $\psi_2$ such that $\psi_1(i)+\psi_2(i)= a_i$ for $1\le i \le n$?

In the reference, a severely restricted variant of NUMERICAL 3-DIMENSIONAL MATCHING (RN3DM) was proven to be strongly NP-complete.


  RN3DM, Given a multiset $U = \{u_1, . . . , u_n\}$ of integers and an integer $e$ such that $\sum_{j=1}^n  u_j +
n(n + 1) = ne$ , do there exist two permutations $\lambda$ and $\mu$ such that
  $u_j + \lambda( j ) + \mu( j ) = e$, for $j = 1, . . . , n$?


There is an easy reduction from RN3DM to $2$-Numerical Matching with target sums problem:
Given an instance of RN3DM. We construct the corresponding instance by making $a_i= e-u_i$ for $1 \le i \le n$

W. Yu, H. Hoogeveen, and J. K. Lenstra.
Minimizing makespan in a two-machine flow shop with
delays and unit-time operations is NP-hard. Journal of
Scheduling, 7:333–348, 2004

EDIT Oct. 1st: Your problem is called PERMUTATION SUMS. It is listed since 1998 in OPEN PROBLEMS IN COMBINATORIAL OPTIMIZATION by Steve Hedetniemi.