Algorithms: Spring '05
From SubfireWiki
Question Harder 1
Defn. NP-complete: 
To prove: 
We know 
and 
, thus, if L'' were solvable in polynomial time, then L would have to be solvable in polynomial time, however L is not.
Question Harder 2
- -------------0 i=0,j=0
- edit[i,j] = edit[i-1,0]+1 when i>0
- -------------edit[0,j-1]+1 when j>0
- -------------min{edit[i,j-1]+1,edit[i-1,j]+1,edit[i-1,j-1]+r(i,j) i,j>0
- r(i,j)=0 when s[i]=t[j] otherwise 1
![\textrm{edit}[i,j] = \begin{cases}
\textrm{edit}[i-1,0]+1 & i>0 \\
\textrm{edit}[0,j-1]+1 & j>0 \\
\min\{\textrm{edit}[i,j-1]+1,\textrm{edit}[i-1,j]+1,\textrm{edit}[i-1,i-1]+r(i,j)\} & i,j>0
\end{cases}](/upload/math/c/e/1/ce141699ff41fd3504aef7fccf8dbabf.png)
![r(i,j)= \begin{cases}
0 & s[i]=t[j] \\
1 & \textrm{otherwise}
\end{cases}](/upload/math/4/5/1/451b2cb64b52e34f5d745585b4f33712.png)
