Outside Computation with Superior Functions (2021)

Abstract: We show that a general algorithm for efficient computation of outside values under the minimum of superior functions framework proposed by Knuth (1977) would yield a sub-exponential time algorithm for SAT, violating the Strong Exponential Time Hypothesis (SETH).

## introduction weighted deduction systems are used in a number of nlp applications, including parsing for contextfree grammars @xcite @xcite and machine translation @xcite . in these applications, the inside-outside algorithm enables efficient calculation of the total weight of all derivations passing through a specific item in the weighted deduction system by computing tables of inside and outside values. @xcite develops a generalized inside-outside algorithm that can be used with any commutative semiring. applying the sum-product semiring results in the standard inside-outside algorithm used as a subroutine in expectation maximization @xcite . applying the max-product semiring results in an efficient algorithm for finding, for example, the best tree that incorporates a specified constituent covering a specified span of the input string. the minimum of superior functions framework of @xcite is an alternative to the semiring framework for analyzing weighted deduction systems. knuth's framework is more general than semirings in that it allows more general functions to be used for combining the weights of subderivations. knuth's framework has the advantage that it allows for best-first search with a generalization of dijkstra's algorithm, as well as for a * search @xcite . given that knuth's framework guarantees efficient inside computation, does it also guarantee efficient outside computation, allowing for a generalized inside-outside algorithm? in this paper, we answer this question in the negative. we prove that a general algorithm for efficient outside computation in this framework would imply the existence of a subexponential time algorithm for satisfiability of boolean formulas in conjunctive normal form (sat), violating the strong exponential time hypothesis (seth) @xcite which postulates that no such algorithms exist. this result may be counterintuitive, because one might expect efficient outside computation to be possible whenever efficient inside computation is possible. we believe this result to be the first formal hardness proof for outside computation in weighted deduction systems. to show both the rule and the weights of the antecedents and consequent, we use a notation where each item's weight is written to its left. this is exemplified in figure 1 , which shows an example rule for cfg parsing with items of the form [a, i, j], representing a subtree rooted by nonterminal a and spanning input tokens i + 1 through j. one item in the weighted deduction system is designated as the goal item, and the fundamental problem is to calculate the total weight of all derivations of this item, where the total weight is calculated using a generalized sum operation, written . an extension of this is to calculate the total weight of all derivations of the goal item g that also contain item x, written γ(x) @xcite : gildea (2020) discussed classes of weighted deduction system where computation of outside values (and by extension, γ values) can be done efficiently. formally, they were interested in systems where γ(x) can (or cannot) be calculated for every item x in time o(|e|γ), where |e| is the number of rules in the system, and γ = max x |γ(x)| is the largest number of bits required to represent the total weight of an item. they termed this "efficient outside computation." one important class of weighted deduction system is the minimum of superior functions @xcite . in this framework, each rule weight function f r is a superior function, meaning that it is monotonically increasing in each argument and the result is always greater than or equal to each of its arguments. the generalized sum in this framework used for calculating total weight is the minimum operation: best-first search is possible in this framework using a generalization of dijkstra's algorithm @xcite . it is interesting to ask whether efficient outside computation is always possible within this framework, and even more generally, whether the conditions necessary for best-first search are sufficient for efficient outside computation. the a* parsing system of @xcite is an instance of the minimum of superior functions framework 1 that uses best-first search. outside values are of particular interest for a* parsing because they can be used as admissible search heuristics @xcite , and to efficiently find the k best parses @xcite . when the function f r simply takes a product of its arguments, as in @xcite , efficient outside computation is possible. in this paper, we address the question of whether this is guaranteed by the minimum of superior functions framework or merely an artifact of this particular system. gildea (2020) pointed out that there is no known efficient algorithm for outside computation in the minimum of superior functions framework. however, they did not present a formal hardness result. in this work, we prove that general efficient outside computation in this framework would yield a subquadratic time algorithm for the orthogonal vectors problem, violating the orthogonal vectors conjecture @xcite , which states that no such algorithms exist because their existence would violate the strong exponential time hypothesis (seth) @xcite and yield a subexponential ## reduction we begin with the orthogonal vectors problem: given sets a, b ⊆ {0, 1} d where |a| = |b| = n, determine whether there exist vectors @xmath0. we now reduce this problem to a weighted deduction system in the minimum of superior functions framework. first, define n axiom items x i , @xmath1, n], and construct n corresponding rules r a i leading from x i to item y : next, we construct n rules r b j,1 , @xmath2, n] of the form: note that while item y could be removed by defining a rule deriving each z j,1 from each x i directly with an appropriately-defined rule weight function, this would require n 2 rules, whereas introducing the intermediate item y provides the same connectivity with only 2n rules while using the weight to keep track of which x i was chosen. this is important because our proof requires that the deduction system used for the reduction be constructed in subquadratic time. now we construct n(d-2) rules r b j,k , @xmath3, n], @xmath4, d -1] of the form: w: z j,k-1 f b j,k (w): z j,k where f b j,k was defined above. the intuition is that each family of z j,k items for a particular j forms a chain that eventually covers all d dimensions of b j . so far we have not covered the final dimension of the b vectors, so we do so now by constructing n rules r b j,d of the form: w: z j,d-1 f b j,d (w): g where g is the goal item of the weighted deduction system. we now discuss properties of the resulting system, a graphical representation of which is presented in figure 2 . every computation begins at one of the axiom items x i corresponding to a i and always passes through y . the computation then proceeds down one of n chains, each corresponding to a vector in b. because the rule weight function f b j,k (w) applied at each edge adds at most 1 to w and each chain from y to g consists of exactly d edges, the weight of any item in the chosen chain will never be more than d greater than the weight of the edge from the chosen x i to y . because each of those edges' weights is a distinct multiple of d + 1, the choice of the starting point (and corresponding vector in a) can be recovered by each f b j,k in the chain using the index(w) function. this allows each chain to effectively calculate the dot product between its respective vector in b and the chosen vector in a. in the superior function framework of @xcite , the total weight of an item c (referred to as γ(c)) is the minimum weight over complete derivations d containing c and the goal item g: for the purposes of the reduction, we are interested in the n total weights γ(x i ). note that every derivation containing x i defines a path from x i to g, and there are exactly n such paths for a given x i : one for each chain from y to g, each corresponding to a vector b j . recalling that weight(x i ) = 0, we can rewrite γ(x i ) as follows: the complete algorithm for solving the problem using this technique is as follows: if all values γ(x i ) could be calculated in linear time with respect to the number of edges |e| ∈ o(nd), then the orthogonal vectors problem could be solved in time o(nd), violating the orthogonal vectors conjecture which states that there is no strongly subquadratic time algorithm for this problem, and by extension violating the strong exponential time hypothesis (seth) @xcite . because the proposed deduction system is an instance of the superior functions framework of @xcite , we conclude that efficient outside computation is not possible in general under that framework unless seth is false. ## conclusion this work provides a formal proof that efficient outside computation is not possible in general for the minimum of superior functions framework @xcite (unless the strong exponential time hypothesis is false). this indicates that the conditions necessary for best-first search are not sufficient for efficient outside computation. it remains an open problem to characterize the class of functions for which best-first search and efficient outside computation are both always possible.