2012/04/10 by Condon, Anne, Maňuch, Ján, Thachuk, Chris
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1204.2201
Given a string w over a finite alphabet Σ and an integer K, can w be partitioned into strings of length at most K, such that there are no collisions? We refer to this question as the string partition problem and show it is \NP-complete for various definitions of collision and for a number of interesting restrictions including |Σ|=2. This establishes the hardness of an important problem in contemporary synthetic biology, namely, oligo design for gene synthesis.