OAI.Superstring.main

The theorem states that there is a function f sending each instance (a finite list of words, where a word is a list of symbols and a symbol is a finite list of bits) to a word, such that two things hold. First, f has a polynomial implementation: there is a deterministic multi-stack Turing machine (a TM2 machine) computing f in polynomial time, measured in bit-level steps in the length of the encoded input, where the instance is encoded as a bit string with prefix markers (false before each list element, true to end each list) and the output word is encoded likewise, and every stack alphabet of the machine is finite. Second, for every instance S, f(S) is a common superstring of S, meaning every word of S occurs in f(S) as a contiguous block of consecutive symbols (the empty word always qualifies), and the length of f(S) in symbols is at most 2 times opt(S), where opt(S) is the least length in symbols of any common superstring of S. This is a factor-two approximation guarantee for shortest common superstring, stated as admitted rather than proved.