  Completely positive, trace preserving (CPT) maps and Lindblad master
equations are both widely used to describe the dynamics of open quantum
systems. The connection between these two descriptions is a classic topic in
mathematical physics. One direction was solved by the now famous result due to
Lindblad, Kossakowski Gorini and Sudarshan, who gave a complete
characterisation of the master equations that generate completely positive
semi-groups. However, the other direction has remained open: given a CPT map,
is there a Lindblad master equation that generates it (and if so, can we find
it's form)? This is sometimes known as the Markovianity problem. Physically, it
is asking how one can deduce underlying physical processes from experimental
observations.
  We give a complexity theoretic answer to this problem: it is NP-hard. We also
give an explicit algorithm that reduces the problem to integer semi-definite
programming, a well-known NP problem. Together, these results imply that
resolving the question of which CPT maps can be generated by master equations
is tantamount to solving P=NP: any efficiently computable criterion for
Markovianity would imply P=NP; whereas a proof that P=NP would imply that our
algorithm already gives an efficiently computable criterion. Thus, unless P
does equal NP, there cannot exist any simple criterion for determining when a
CPT map has a master equation description.
  However, we also show that if the system dimension is fixed (relevant for
current quantum process tomography experiments), then our algorithm scales
efficiently in the required precision, allowing an underlying Lindblad master
equation to be determined efficiently from even a single snapshot in this case.
  Our work also leads to similar complexity-theoretic answers to a related
long-standing open problem in probability theory.
