The complexity of string partitioning

Details The complexity of string partitioning The complexity of string partitioning

2012-04-10

arxiv.org/abs/1204.2201v1

Computer Science

Computational Complexity

14 pages main text + 13 pages appendix. Full version with proofs of an article appearing in the Proceedings of the 23rd Annual

Scientific paper

Given a string $w$ over a finite alphabet $\Sigma$ and an integer $K$, can $w$ be partitioned into strings of length at most $K$, such that there are no \emph{collisions}? We refer to this question as the \emph{string partition} problem and show it is \NP-complete for various definitions of collision and for a number of interesting restrictions including $|\Sigma|=2$. This establishes the hardness of an important problem in contemporary synthetic biology, namely, oligo design for gene synthesis.

Affiliated with

Also associated with

No associations

Rating

The complexity of string partitioning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The complexity of string partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of string partitioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-645597