In this paper we consider the weighted -Hamming and -Edit distances, that are natural generalizations of the classical Hamming and Edit distances. As main results of this paper we prove that for any ≥ 2 the DECIS--Hamming problem is P-SPACE-complete and the DECIS--Edit problem is NEXPTIMEcomplete. In our formulation, weights are included in the instance description and the cost is not uniform.
Measuring how dissimilar two strings are from each other, is a task that occurs often and
which has great importance in various practical fields, such as biometric recognition and
the study of DNA, up to spell checking. A formal treatment of the problem passes through
the definition of a notion of distance between strings. Numerous distance functions have
been proposed and studied from a computational point of view in the literature, based on
the idea of measuring the minimum number of modification operations, chosen in a given
set of admissible operations, necessary to transform one string into another one: two of the
best known are certainly the Edit distance and the Hamming distance, but since 1950 other
distances have been introduced and scientific studies have been carried on (cf. for instance
[
In this paper we consider, among others, an operation that replaces two consecutive characters with other two ones. Clearly this kind of operation includes the swap operation. We will discuss more details on this subject in Section 4.
In this framework, measuring how similar two strings are is then formalized as an optimization problem, i.e. minimizing the amount of operations to transform one into the other one. It is quite useful to also consider the decision version of such problem, in the following way: in any instance there are two words together with a natural number ℎ and we ask whether or not the two given words have a distance (Hamming, edit or another one) that is smaller than or equal to ℎ.
Previous approach could seem well formalized but there is something hidden: is the description (i.e. the cost of each operation) of the distance (Hamming, edit or another one) included inside the instances of the problem or the description of the distance has to be considered as a constant that can vary depending on the problem but that should not be considered in the asymptotic analysis of the algorithms that solve the problems? Usually the second approach is the one that seems preferred in literature. For instance we say that the complexity of the classical algorithm for the edit distance is (), where and are the lengths of the two strings.
On the contrary something diferent happens in some cases. In [ 21] it is proved that including
the description of a special distance inside the instances gives rise to an NP-hard problem,
whilst much later it has been proved that there is a polynomial-time algorithm for the same
problem, when the size of the description of the distance is considered as a constant [
In this paper we study the problems of computing the -Hamming and the -Edit distances, for ≥ 2, in the first setting, i.e. we suppose that the description of the distance, that includes all costs of all operations, is a part of the instances. The study of these problems following the second approach is still open, as discussed in Section 4.
In Section 2 we introduce our notation and some formal definitions. Section 3 is devoted to prove that, for ≥ 2, the decision problems of computing the -Hamming (DECIS--Hamming) and the -Edit (DECIS--Edit) are, respectively, P-SPACE-complete and NEXPTIME-complete. To do so, we follow the same strategy for both problems because, in such a way, the proofs are more natural and easier to follow. First we prove the results for = 3, using polynomial time reductions from any ∈ P-SPACE to DECIS-3-Hamming and from any ∈ NEXPTIME to DECIS-3-Edit, and straightforwardly extend them to larger values of . Then we reduce (in polynomial time) the problems with = 3 to the respective problems with = 2, proving the results also for these cases. Section 4 concludes the paper foreshadowing possible research developments.
Given a finite alphabet Σ of cardinality , a string over Σ is a sequence = 12 . . . , with ∈ Σ, for any 1 ≤ ≤ . The number of characters composing a string is called its length, denoted by || = . The string of length 0, also called the empty string, is indicated by . We denote by Σ* the set of all strings on Σ and by Σ the set of all strings of length in Σ* . Trivially ∈ Σ* , for any Σ. String is a substring of string if there exist and such that it is possible to write as the concatenation of , and i.e., such that = . The empty string is a substring of any string.
Given a string , it is possible to define a set = { : Σ* → Σ* } of operations that allow to modify it in a new string . Some well-studied subsets of operations are the edit operations:
Given a string ∈ Σ* , we define: • Insertion (I, → ) allows to insert a character ∈ Σ in a position of , i.e. = 1 . . . − 1 . . . ||; • Deletion (D, → ) is the removal of character = in , i.e. = 1 . . . − 1+1 . . . ||; • Substitution (S, → ) replaces character = in with another character ∈ Σ in the same position, i.e. = 1 . . . − 1+1 . . . ||.
We describe here another operation that allows to define some more distances. 1 . . . − 11 . . . + . . . ||.
Definition 2. Given a string ∈ Σ* , we define -Substitutions as follow: -Substitution (S, 1 . . . → 1 . . . ) allows substitutions of consecutive characters all at once. It replaces in the substring 1 . . . = . . . +− 1 with 1 . . . , i.e. =
Obviously in Definition 2, is a generalization of the operations, e.g. = if = 1. Notice also that the classical swap operation (see [23] for a formal definition) is a special 2-Substitution.
For the sake of readability, we henceforth use the notation = {1, . . . , }, with 1, . . . , ∈ {, , | ∈ Z+} to indicate that all the possible operations defined by each are in , e.g. = {} allows all the insertions → with ∈ Σ.
At this point, we can define a cost function : → Z+ for each operation. That cost can be constant or non uniform i.e. it can depend on the operation on which it is applied. More general operations, that includes the ones considered in this paper, have been studied in [19, Section 4].
Notice that, from a formal point of view, all the above operations should have as parameters the positions where they are applied, even if their cost does not depend on them. However, we prefer to not be strictly formal in order to improve the readability of the text. Definition 3. Let , ∈ Σ* be two strings, be a set of operations defined on Σ* , be an arbitrary cost function. If = 12 . . . is a sequence of operations over , the overall cost of the sequence is: ( ) = ∑︁ ().
=1 The distance between and is the minimum cost required to transform into through a sequence of operations in , i.e. if () = (. . . (2(1())) . . .) (, ) = min{ ( ) | () = }. (1)
Depending on the set of operations we can define diferent distances.
The Edit distance between and is (, ), considering = {, , }.
The Edit distance is also formally known as Levenshtein distance, due to the work carried out by Vladimir Levenshtein who introduced for the first time an algorithmic approach to calculate this distance [14].
Definition 5 ([13]).
We define Hamming distance between and (, ), when = {}.
Apart from the well-studied Edit Distance and Hamming Distance, it is possible to define some other distances between strings such as the following ones, that are special cases of the maximal generalization given in [19].
Definition 6 ( 2-Edit Distance). The 2-Edit distance between two strings and is the minimum cost to transform the string into , (, ), setting the set of admissible operations = {, , , 2}.
Obviously, 2-Edit Distance is a direct extension of the previously defined Edit distance, with the addition of the double substitution operation.
Last but not least we define the generalizations of 2-Edit and Hamming distances, the -Edit and -Hamming distance, respectively, for an integer ≥ 2.
Definition 7 ( -Edit Distance, -Hamming Distance). Given two strings and and an integer ≥ 2, • the -Edit distance between and is (, ), with = {, , , S}.
• the -Hamming distance between and is (, ), with = {S}.
We prove in this section that DECIS-3-Hamming problem is P - SPACE-complete. DECIS-3Hamming contains all the strings encoding quadruples of the form < , , , ℎ > where and are two strings on Σ of the same length , is an encoding string that describes the weighted 3-Hamming distance we are considering, ℎ is an integer and (, ) ≤ ℎ.
Hence, an instance =< (, , , ℎ) > fits into DECIS- 3-Hamming if and only if (, ) ≤ ℎ. Therefore
DECIS-3-Hamming = {< (, , , ℎ) >: (, ) ≤ ℎ}.
In order to say that DECIS-3-Hamming is P-Space complete, we need to prove the two following properties: a) DECIS-3-Hamming is in P-Space; b) for every language in P-Space there exists a polynomial reduction from to DECIS-3-Hamming.
Theorem 1. DECIS-3-Hamming is in P-Space.
Proof. By a corollary to Savitch’s Theorem [24] we know that P-Space=NP-Space. Hence, proving that the problem is in NP-Space will be enough to prove the Theorem.
We define a Nondeterministic Turing Machine that accepts the DECIS-3-Hamming language in polynomial space, even in the worst case. starts with < , , , ℎ > coded on its tape and operates iteratively. In each loop, it non-deterministically chooses a substitution to apply to the string, executes it and updates ℎ by subtracting the weight of the substitution just chosen. exits the while loop when becomes equal to or ℎ is negative. In both cases it will be possible to establish whether the given instance belongs to DECIS-3-Hamming. It is possible to observe that the total occupied space is linear with respect to the length of the input strings, hence DECIS-3-Hamming is in NP-SPACE, and, therefore, in P-SPACE.
1. begin 2. while ̸= ∧ ℎ ≥ 0 3. non-deterministically choose a substitution to apply; 4. apply the substitution to string ; 5. subtract the weight of the substitution from ℎ; 6. if == ∧ ℎ ≥ 0 7. ACCEPT 8. else 9. DO NOT ACCEPT 10. end Algorithm 1: Algorithm followed by for solving DECIS-3-Hamming □ Theorem 2. For each language in P-SPACE there is a polynomial time reduction from to DECIS-3-Hamming.
Proof. If is in P-SPACE there exists a deterministic Turing machine
=< , Γ, , Σ, Δ, 0, > that stops on every input of size in (()) time and decides in polynomial space (()), being a constant and and two polynomials.
We define ′ as the Turing Machine that accepts the DECIS-3-Hamming language. We define an algorithm for mapping each instance in into an instance ′ =< (, , , ℎ) >, such that accepts if and only if ′ accepts ′. We formally define the parameters of instance ′ as follows.
• = $()+10()+1$, where $ ∈/ Γ; • = $$ with = 2() + + 3; • ℎ = min{ > () + 2() + 4 + }. This value of ℎ can be represented in base as the string obtained by the concatenation of 1 and times 0, with = ⌈log () + 2() + 4 + ⌉.
The last parameter to define is the distance . We note immediately that the description of the distance is independent of , therefore it is constant with respect to . This distance is a weighted 3-Hamming that assumes only two weights 1 and ℎ + 1. To give the full description of we would need to define the weight for all 3-substitutions. For each ∈ Γ the following 3-substitutions with cost 1 are produced: • every transition Δ(ℎ, ) = ( , , ) in produces ℎ → in ; • every transition Δ(ℎ, ) = ( , , ) in produces ℎ → in ; • every transition Δ(ℎ, ) = ( , , ) in produces ℎ → in ; • every transition Δ(ℎ, ) = ( , , ) in produces ℎ → in .
In addition, the following 3-substitutions with cost 1 are added, for each ∈ and , ̸= $, with #, # ∈/ Γ.
• → ## • # → # • $# → $ • # → # • #$ → $
This set of 3-substitutions is required if a ∈ appears on the simulated tape. In fact, it is used to erase the entire tape. For the remaining undefined 3-substitutions we set the cost to ℎ + 1. □
It is possible to observe that the algorithm is polynomial.
Theorem 3. Let be an instance in ∈ P-SPACE, the transformation of in ′ just defined is a reduction, i.e.
∈ ⇐⇒ ′ ∈ DECIS-3-Hamming.
Proof. Suppose first that ∈ . This means that there exists a finite sequence of ID 1 . . . such that 1 = 0, for any < < () ⊢ +1 and is a final ID. For each implication from one ID to another one there is a corresponding transition rule which can be simulated by a substitution of unit weight in the distance , as previously described. Formally we match 1 to the string and at the end of the simulation we will have reached which will correspond to a string ′ containing . In this way we will be able to say that there exists a sequence of substitutions of unitary weight in which, starting from , allows us to arrive at ′ with a total weight less than (). Using, at this point, the substitutions of unitary weight that cancel the symbols diferent from $ and around we will obtain the string = $$, with = 2() + + 3. In total, therefore, the cost of obtaining is less than or equal to () + 2() + + 4 and therefore less than ℎ. So ′ ∈ DECIS-3-Hamming.
Let us prove now the converse. We do it by contraposition. If ̸∈ then there is no sequence of transitions that can lead the initial ID to an ID in which a final state appears. In the simulation using 3-substitutions, no sequence of substitutions of unitary weight can ever transform the string into a string ′ containing a final state and therefore cannot be obtained. The only way to get an accepting state on the tape would be to use a substitution costing ℎ + 1. But in this case the 3-Hamming distance between and will certainly be greater than ℎ, so ′ ̸∈ DECIS-3-Hamming. □ Theorem 4. Any DECIS--Hamming, with ≥ 3, is P-SPACE-complete.
Proof. It is easy to observe that the previous proof can be used to demonstrate, by induction, the P-SPACE-completeness of any DECIS--Hamming problem, with ≥ 3, since: a) Algorithm 1 works for any DECIS--Hamming; b) There exists a polynomial time reduction from DECIS-Hamming to DECIS-( + 1)-Hamming ( ≥ 2). The reduction has just to pad input and target string (to handle strings with length + 1) and to inhibit any ( + 1)-substitution that does not represent a -substitution. □
In this section we prove that also DECIS-2-Hamming is P-Space Complete. We first define the following set, for any ∈ Z+ and , ∈ Σ:
DECIS’--Hamming = {< , , , ℎ > | (, ) ≤ ℎ, ( → ) ∈ {1, ℎ + 1}} Notice that the proof of P-Space-completeness of DECIS-3-Hamming holds for DECIS’3-Hamming, too. In fact we have that: a) DECIS’-3-Hamming is a special case of DECIS-3Hamming, thus the Algorithm 1 is valid; b) the reduction defined in Theorem 2 actually produces instances of DECIS’-3-Hamming.
We can, therefore, state the following lemma.
Lemma 1. DECIS’-3-Hamming is P-Space-Complete.
It is also worth noting that an algorithm similar to Algorithm 1 can be defined for DECIS- 2Hamming, thus: Lemma 2. DECIS-2-Hamming ∈ P-Space.
Lemma 3. There is a reduction from DECIS’-3-Hamming to DECIS-2-Hamming. Proof. It is possible to prove this reduction thanks to a technique which belongs to the folklore of Information Theory and to Markov chains. This technique reduces the dependence of a random variable on previous random variables, including itself, to just two random variables, including itself, via a sliding window over a larger alphabet.
Let =< , , , ℎ > be an instance in DECIS’-3-Hamming, we transform it into an instance ′ =< ′, ′, ′, ℎ′ > in DECIS-2-Hamming, where • ′ = 12 . . . +1 is obtained from = 12 . . . , by: – $-padding , i.e. ¯ = 12 . . . +2 = $$; – coding any symbol of ′ as a pair of consecutive symbols of ¯, obtained with a sliding window of length 2 and stride 1, i.e. = (, +1) • ′ is constructed from in an analogous way; • ℎ′ = 3ℎ; • for each 3-substitution → , with substitutions are added to ′:
()(); – ()() → (←)()→ – ()(←)() → ()(), ∀ ∈ Σ ∪ {$} – (→)()() → ( )( ), ∀ ∈ Σ ∪ {$} • any other 2-substitution has cost ℎ′ + 1 = 1 in , the following unit cost 2
The algorithm is polynomial in the size of the input, indeed: a) |′| = ||+1 and |′| = ||+1; b) coding ℎ′ = 3ℎ requires linear time; c) the algorithm increases the size of the alphabet with a polynomial function and coding ′ requires (|Σ′|2) steps.
Moreover, it is possible to observe that the algorithm is a reduction, i.e.:
∈ DECIS’-3-Hamming ⇐⇒ ′ ∈ DECIS-2-Hamming
Suppose ∈ DECIS’-3-Hamming, i.e. ∃ = 1 . . . .. () = , ( ) ≤ ℎ, with each ∈ . Then, ∃ ′ = ′1 . . . ′3 .. ′(′) = ′, ( ′) ≤ ℎ′, with each ′ ∈ ′. ′ is obtained by , by translating each into the corresponding sequence of 2-substitutions described by the algorithm, thus
∈ DECIS’-3-Hamming ⇒ ′ ∈ DECIS-2-Hamming
Suppose ∈/ DECIS’-3-Hamming, i.e. ∀ = 1 . . . .. () = , ( ) > ℎ, with each ∈ . Since the algorithm, by construction, do not insert any (←)() or (→)() symbols in ′, the only way to obtain ′ from ′ is to remove all these symbols from the string, thus completing simulated (and legal) 3-substitutions in the input instance. Therefore, ∀ ′ .. ′(′) = ′, ( ′) > 3ℎ, thus ∈/ DECIS’-3-Hamming ⇒ ′ ∈/ DECIS-2-Hamming □
These lemmas imply the following result.
Theorem 5. Decis-2-Hamming is P-Space-Complete.
We will now prove that DECIS-3-Edit distance is NEXPTIME-complete, that is: a) DECIS-3Edit ∈ NEXPTIME; b) ∀ ∈ NEXPTIME, there exists a polynomial time reduction from to DECIS-3-Edit.
Theorem 6. DECIS-3-Edit ∈ NEXPTIME Proof. We show a Nondeterministic Turing Machine that, given =< (, , , ℎ) > in input, accepts if and only if (, ) < ℎ. acts as described in Algorithm 2. Theorem 7. ∀ ∈ NEXPTIME, there exists a polynomial time reduction from to DECIS-3-Edit Proof. If ∈ NEXPTIME, there exists a Nondeterministic Turing Machine ′ =< , Γ, , Σ, Δ, 0, > that recognizes if ∈ and stops within an exponential number of moves, i.e. if = ||, it will halt after 2() steps at most, where () is a polynomial function of . The reduction transforms any instance for in an instance ′ =< (, , , ℎ) > for DECIS-3-Edit as follows: • = $0$, with $ ∈/ Γ • = $$ • ℎ = 5 * 2() + 2 * ( + 1) Finally, is defined in the following way: 1. any insertion has cost = ℎ + 1, with the exception of → 1 (being 1 ∈/ Γ a new blank symbol), that has cost = 1; 2. any deletion has cost = ℎ + 1, with the exception of * → , that costs = 1, where * ∈/ Γ is a new symbol used to delete the simulated tape after the acceptance of ′; 3. any substitution has cost = ℎ + 1 4. any 3-substitution has cost = ℎ + 1, with the following exceptions: a) for each element of {< (, ), (, , ) > |(, , ) ∈ Δ(, )}, with and state symbols not in Γ and , ∈ Γ: i. → , with ∀ ∈ Γ, has cost = 3; ii. $ → $, with ∀ ∈/ , has cost = 1; iii. $ → $, with ∀ ∈ , has cost = 3; b) for each element of {< (, ), (, , ) > |(, , ) ∈ Δ(, )}, with and state symbols not in Γ and , ∈ Γ: i. → , with ∀ ∈ Γ, has cost = 3; ii. $ → $, with ∀ ∈ , has cost = 1; c) to simulate moves that require to expand the tape length behind ||, the following 3-substitutions have cost = 1: i. 1$ → $; ii. $1 → $; d) to delete symbols and reach the target string $$ after the acceptance ′, with ∈ and , ∈ Γ, the following 3-substitutions have cost = 1: i. → # * #; ii. $ → $ * #; iii. $ → # * $; iv. $$ → $ * $; v. #* → # * * ; vi. * # → * * #; vii. $#* → $ * * ; viii. * #$ → * * $.
The algorithm takes polynomial time (): writing and requires linear time in , while coding would take (|Γ|6). Moreover, it is actually a reduction, i.e.:
∈ ⇐⇒ ′ ∈ DECIS-3-Edit.
Suppose ∈ . There exists a finite sequence of non-deterministic moves (and, therefore, of IDs) that makes ′ accept . It is easy to see that there is a corresponding sequence of transformations that modifies and results in the string $$, with , ∈ Γ* and ∈ . Each 3-substitution that simulates a ′ move has cost = 3, if it does not involve the $ symbol (or if it ends in a final state symbol within the $ symbols), otherwise it has cost = 1 if it results in one of the strings: $$ ( ∈/ , ∈ Γ* ), $$ ( ∈ Γ* ). In the latter cases has a reduced value because the insertion of 1 (point 1) and a further 3-substitution are needed to obtain a string that correctly represents the output ID. In any case, a move of ′ is simulated by a sequence of transformation , such that () = 3, and, therefore, a sequence of moves from the initial ID to an accepting one can be simulated with a total cost 3 * 2(). At this point, a sequence of 3-substitutions has to be applied to transform all the symbols within the two $ into * . They are + 1 + 2() at most and each 3-substitution adds one * at unitary cost. Thus, the whole sequence has cost ≤ + 1 + 2(). Finally, the same cost is required by the sequence of deletions that results in the string $$. Thus,
∈ ⇒ ($0$, $$) ≤ ℎ.
Suppose now ∈/ . Any 3-substitution that does not correspond to a legal move of ′, or is part of it, has cost ℎ + 1, with the exception of those used to transform symbols into * and they can be applied only when the simulated ID is an accepting one. The same holds for deletion of * symbols. Thus, all the sequences of transformations from $0$ to $$ have cost > + 1 + 2(), i.e.: ∈/ ⇒ ($0$, $$) > ℎ □ Theorem 8. Any DECIS--Edit, with ≥ 3, is NEXPTIME-complete.
Proof. The proof is analogue to that of Theorem 4. It is easy to demonstrate, by induction, the NEXPTIME-completeness of any DECIS--Edit problem, with ≥ 3, since: a) Algorithm 2 works for any DECIS--Edit; b) There exists a polynomial time reduction from DECIS--Edit to DECIS-( + 1)-Edit ( ≥ 2). Again, the reduction has to inhibit any ( + 1)-substitution not representing a -substitution. □
We now prove the NEXPTIME-completeness of DECIS-2-Edit. To prove that DECIS-2-Edit ∈ NEXPTIME, one can employ the same algorithm given in Section 3.3 (Algorithm 2). Instead of explicitly showing that exists a polynomial time reduction from any problem in NEXPTIME to DECIS-2-Edit, we show a polynomial time reduction from a NEXPTIME-complete problem. Indeed, we proved in Section 3.3 the NEXPTIME-completeness of DECIS-3-Edit, but the same proof actually holds for a restricted version of the problem, named DECIS’-3-Edit, where for each instance < , , , ℎ >: a) any insertion, deletion or substitution costs either 1 or ℎ + 1; b) 3-substitutions costs are limited to 1, 3 or ℎ + 1.
Therefore, to prove the NEXPTIME-completeness of DECIS-2-Edit, it is suficient to show a reduction from DECIS’-3-Edit to it.
Theorem 9. There exists a polynomial time reduction from DECIS’-3-Edit to DECIS-2-Edit. Proof. The reduction transforms any instance =< (, , , ℎ) > for DECIS’-3-Edit in an instance ′ =< (, , ′, 5ℎ) > for DECIS-2-Edit as follows: 1. if Σ is the alphabet of the input instance, Σ′ for the output instance is augmented by adding the following new symbols: a)
()(), ∀, , , , , ∈ Σ, ∈ {1, 2, 3}; b) the supporting symbol * ; 2. for each → ∈ s.t. ( → ) = 1, add → , with = 5, in ′; 3. for each → ∈ , s.t. ( → ) = 1, add → , with = 5, in ′; 4. for each → ∈ s.t. ( → ) = 1, add → , with = 5, in ′ 5. for each 3-substitution → ∈ s.t. ( → ) = ≤ ℎ, add the following operations to ′: a) → (1)(), with = 5 − 4; b) (1)() → (2)(), with = 1; c) (2)() → (3)(), with = 1; d) (3)() → * , with = 1; e) * → , with = 1; 6. any other operation has cost 5ℎ + 1 in ′.
The algorithm requires polynomial time. Source and target strings are unchanged, the limit ℎ has to be multiplied by 5 and the size of the alphabet (and of ′) is increased by a polynomial function: |Σ′| = (|Σ|6).
We can observe that the algorithm is actually a reduction, i.e:
∈ DECIS’-3-Edit ⇐⇒ ′ ∈ DECIS-2-Edit
Suppose =< , , , ℎ >∈ DECIS’-3-Edit, i.e. ∃ .. () = , ( ) ≤ ℎ. Let = 12 . . . : it is possible to “simulate” each on ′ with a sequence of one or more operations ′ at cost (′) = 5 * (). Insertions, deletions and substitutions require a single operation, while, for 3-substitutions, the whole sequence of operations described at point 5 is needed, with total cost of 5, where is the original 3-substitution cost. Therefore, =< , , , ℎ >∈ DECIS’-3-Edit ⇒ ′ =< , , ′, 5ℎ >∈ DECIS-2-Edit On the other hand, suppose =< , , , ℎ >∈/ DECIS’-3-Edit. It can be observed that each operation on ′ either: • has cost larger than 5ℎ + 1 and can not be part of an acceptable sequence; • corresponds to an operation on , with cost 5 * (); • is part of a 3-substitution simulation. Each step of the sequence can be executed only after the previous and the first step introduces a symbol that can not be part of ′. The only possibility to remove “exogenous” symbols is to apply all the operations in the sequence, at cost 5 * (), where is the simulated 3-substitution.
Therefore, =< , , , ℎ >∈/ DECIS’-3-Edit ⇒ ′ =< , , ′, 5ℎ >∈/ DECIS-2-Edit □
In this work we studied the computational complexity of the problems of computing the cost of the -Hamming and -Edit distances, for ≥ 2, proving that the decision versions that include the description of the distance as part of the instances are, respectively, P-SPACE-complete and NEXPTIME-complete. Negative results as these ones are of theoretical relevance but can also facilitate further researches, as discussed in the following.
We have some preliminary results, not included in this paper, for some special cases where the size of the description of the distance is considered constant. For instance, we found a polynomial time algorithm to compute the 2-Hamming distance when every operation has the same constant cost.
It is an open problem to find the complexity of solving both problems as the lengths of the
two words increase when the distance is fixed, or, more generally, when the complexity is
further parameterized analogously as done in [
This new open problem is thus connected with the forty-year open problem contained in [23], since swap operations are special 2-Substitutions.
Our results suggest that if polynomial algorithms exist, they must non-polinomially depend on some parameter such as the maximum of the ratio between all possible operations costs.
This research is funded by FONDO FINALIZZATO ALLA RICERCA DI ATENEO (FFR), University of Palermo, year 2023. [11] F. J. Damerau, A technique for computer detection and correction of spelling errors,
Communications of the ACM 7 (1964) 171–176. [12] S. Faro, A. Pavone, K. Steinhofel, An eficient skip-search approach to swap matching,
The Computer Journal 61 (2018) 1351–1360. [13] R. W. Hamming, Error detecting and error correcting codes, The Bell system technical journal 29 (1950) 147–160. [14] V. I. Levenshtein, Binary Codes Capable of Correcting Deletions, Insertions and Reversals,
Soviet Physics Doklady 10 (1966) 707–710. [15] D. Meister, Using swaps and deletes to make strings match, Theoretical Computer Science 562 (2015) 606–620. [16] S. C. Sahinalp, Edit distance under block operations, in: M.-Y. Kao (Ed.), Encyclopedia of
Algorithms, Springer US, Boston, MA, 2008, pp. 265–267. [17] D. Shapira, J. A. Storer, Edit distance with move operations, Journal of Discrete Algorithms 5 (2007) 380–392. 2004 Symposium on String Processing and Information Retrieval. [18] D. Shapira, J. A. Storer, Edit distance with block deletions, Algorithms 4 (2011) 40–60.
doi:10.3390/a4010040. [19] E. Ukkonen, Algorithms for approximate string matching, Information and Control 64 (1985) 100–118. doi:10.1016/S0019-9958(85)80046-2, International Conference on Foundations of Computation Theory. [20] R. A. Wagner, On the complexity of the extended string-to-string correction problem, in: Proceedings of the seventh annual ACM symposium on theory of computing, 1975, pp. 218–223. [21] R. A. Wagner, M. J. Fischer, The string-to-string correction problem, Journal of the ACM (JACM) 21 (1974) 168–173. [22] R. A. Wagner, R. Lowrance, An extension of the string-to-string correction problem,
Journal of the ACM (JACM) 22 (1975) 177–183. [23] R. A. Wagner, On the complexity of the extended string-to-string correction problem, in: D. Sankof, J. B. Kruskal (Eds.), Time Warps, String Edits, and Macromolecules The Theory and Practice of Sequence Comparison, Addison-Wesley Publishing Company, 1983, pp. 218–223. [24] W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4 (1970) 177–192.