[klmr]

No, a given assembly is easy to verify. The complexity in actual application comes from the fact that performing the sequencing part (the biological/mechanical part) again will yield a different assembly due to biological and technical variability. Another complexity comes from the fact that you can define different measures of “goodness” (and hence optimality), depending on which errors you model.

But from a computational standpoint, sequence assembly (using a given error metric) is simply NP-hard.