Closest string problem Instance: Given a set B of n strings of length L, and an integer d Objective: Find a string s of length L such that for each string s∈B,a(s,s;)≤d Theorem: Closest string problem is NP-hard. (Lanctot, Li, Ma, Wang, Zhang, 1999) 2021/1/29 82021/1/29 8 Closest String Problem Instance: Given a set B of n strings of length L, and an integer d Objective: Find a string s of length L such that for each string si  B, d(s, si )  d Theorem: Closest string problem is NP-hard. (Lanctot, Li, Ma, Wang, Zhang, 1999)