Additional Discussion & Typos

Description: There have been a few cases where readers have requested additional information or clarification in regards to something in my doctoral dissertation. This document was created to provide additional information, clarifications, and address any typos.


Case 1: Found by VZN on 2-21-17

At the end of page 2 continuing on to the next page, the following is stated:

"Then, Karakostas, Lipton, and Viglas (2003) connected the hardness of intersection non-emptiness to the hardness of Boolean Satisfiability [36]. They showed that if the parameterized intersection problem for k DFA's is solvable in n^o(k) time, then the exponential time hypothesis is false."

Correction: Karakostas, Lipton, and Viglas (2003) showed that if intersection non-emptiness is solvable in n^o(k) time, then for every e > 0, SUBSET SUM is solvable in 2^{en} time and NTIME(n) is a subset of DTIME(2^{en}). However, they do not explicitly connect intersection non-emptiness to Boolean Satisfiability or ETH.

More recently, in Fernau and Krebs (2016), it is shown that if intersection non-emptiness is solvable in n^o(k) time, then ETH fails. We expand on this result in both subsections 7.2.2 and 7.2.3 of the dissertation.


Case 2: Typos found on 3-23-17

Typo: On page 47 near the top of the page, it says, "Let a c-uniform hypergraph H with vertices {v_i}_[n] be given." The family of vertices should be written as {v_i}_{i \in [n]} meaning the family of vectors of the form v_i for all i in [n].

Typo: On page 47 near the bottom of the page, it says, "The reduction is related to the reductions from Theorem 8 and 9." It is referring to Theorems 8 and 9 from reference [69]. These theorems can also be found in Chapter 7 (see Theorems 7.22 and 7.23).


Case 3: Added on 5-12-17 in response to helpful comments from Turbo

Informal Discussion: A fixed level of a parameterized problem is a decision problem that is obtained by fixing the value of the parameter.

The complexity of the fixed levels of a parameterized problem may differ from the complexity of the parameterized problem. For example, it is possible that there could exist an efficient algorithm for every fixed level, yet there does not exist an efficient algorithm for the parameterized problem.

One may equivalently view this as the difference between the existence of a non-uniform algorithm vs a uniform algorithm. The existence of a non-uniform algorithm is weaker than the existence of a uniform algorithm.

In this work, we consider the complexity of fixed levels of parameterized problems and the complexity of the parameterized problems themselves. In the latter case, we try to explicitly write the term uniform algorithm and enclose the problem abbreviation in parentheses.


Case 4: Typos found on 9-26-17

Typo: Page 64 under "Exact Time Complexity". It should say, "Intersection non-emptiness problem for 3k unary DFA's can be solved in n^1.4k time by a reduction to triangle finding in a sparse graph." The coeficient "3" was missing in the original sentence.

Recently, an improved algorithm was found running in roughly n^1.1865k time. This will appear in an upcoming paper.

Update on 9-29-18: The paper with the improved algorithm is titled "Intersection Non-Emptiness and Hardness within Polynomial Time" (DLT 2018)

The paper also provides a reduction from triangle finding for a graph with n vertices and m edges to intersection non-emptiness for two DFA's. The resulting DFA's have O(n log(n)) and O(m log(n)) states. It's not entirely clear if this can be improved to DFA's with O(n) and O(m) states as stated on page 64 under "Hard Problems in Polynomial Time".


Case 5: Typo found on 6-12-18

Typo: Page 20 under "3.2.1 Symmetric Automata". It should say, "A symmetric finite automaton...", instead of "A symmetric finite automata...".


Case 6: Clarification on 10-22-18

Clarification: Page 21 proof of Theorem 3.12. This argument assumes that the symmetric NFA's are allowed to have missing transitions. In particular, if we are at a state and read an alphabet character that has no transition, then the automaton rejects the string. After rejection, the computation is over meaning that it can't read the reversal of the character and keep going.


Case 7: Typo found on 8-20-21

Typo: Page 12 above Theorem 2.2. It should cite both [46] and [57] as is done on the bottom of page 20.


Please feel free to send me questions and I will add additional discussion here when appropriate. Thank you very much for reading.

Back to Homepage