Computation of the Closest string Problem Theorem: Closest string problem is NP-hard (K. Lanctot, M. Li, B Ma, S. Wang, and L Zhang 1999) A 4/3(1+) approximation (K. Lanctot, M. Li, B Ma, S. Wang, and L. Zhang 1999) (. Gasieniec, J. Jansson, and A Lingas 1999) A PTAS was presented for the problem (M.Li, B. Ma, and L. Wang, 1999) 2021/1/29 162021/1/29 16 Computation of the Closest String Problem Theorem: Closest string problem is NP-hard. (K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang 1999) A 4/3(1+) approximation: (K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang 1999) (L. Gasieniec, J. Jansson, and A. Lingas 1999) A PTAS was presented for the problem (M. Li, B. Ma, and L. Wang, 1999)