title: String to string correction problem np-completeness proof
body: <p>I have this assignment to prove that this problem:</p>
  
  <blockquote>
    <p>Finite alphabet £, two strings x,y €
    £*, and a positive integer K.  Is
    there a way to derive the string y
    from the string x by a sequence  of K
    or fewer operations of single symbol
    deletion or adjacent symbol
    interchange?</p>
  </blockquote>
  
  <p>is np-complete. I already figured out I have to make transformation from decision version of set covering problem, but I have no clue how to do this. Any help would be appreciated.</p>