The sorting by strip exchanges (aka strip exchanging) problem is motivated by applications in optical character recognition and genome rearrangement analysis. While a couple of approximation algorithms have been designed for the problem, nothing has been known about its computational hardness till date. In this work, we show that the decision version of strip exchanging is NP-Complete. We present a few new lower bounds for the problem along with the stated result. The
NP-Completeness proof is based on reducing sorting by strip moves, an already known NP-Complete problem, to strip exchanging. The former is a widely studied problem also motivated by optical character recognition
and genome rearrangement analysis.

1. "Department of Computer Science and Engineering" added to affiliation.

2. "Research supported in part by NSF grant CCF-0844796" added as a footnote.

The sorting by strip exchanges (aka strip exchanging) problem is motivated by applications in optical character recognition and genome rearrangement analysis. While a couple of approximation algorithms have been designed for the problem, nothing has been known about its computational hardness till date. In this work, we show that the decision version of strip exchanging is NP-Complete. We present a few new lower bounds for the problem along with the stated result. The
NP-Completeness proof is based on reducing sorting by strip moves, an already known NP-Complete problem, to strip exchanging. The former is a widely studied problem also motivated by optical character recognition
and genome rearrangement analysis.