Genome assembly has long thought to be NP-hard based on combinatorial optimization formulations of the problem such as shortest common superstring. However, when viewed as a reconstruction problem, a natural question is whether the problem remains NP-hard on the information-feasible instances, i.e. when there is enough information to reconstruct the unknown genome. We give an answer to this question, and explore the broader implications on the interplay between information and complexity.