When Is Local Search Both Effective and Efficient?

Local search algorithms start at an initial assignment and successively move to better adjacent assignments until no further improvement is possible. As with all algorithms, we can ask about their effectiveness (“did we find a good solution?”) and efficiency (“did we find it quickly?”). Often, we do not know the precise answers to these questions, but still choose to use local search in combinatorial optimisation [1, 12, 18, 42, 49].¹¹1Sometimes local search is chosen because it is easy to implement. If we do not expect any algorithm to be effective and efficient on all inputs – say for $\mathrm{𝖭𝖯}$-hard combinatorial optimization problems – then why not choose an algorithm that will take less effort to implement and maintain? At other times, local search is forced on us. If we want to understand the evolution of biological systems [30, 31] or of social systems in business [26, 38] and economics [45], or even just energy-minimization in physical systems, then we need to study the effectiveness and efficiency of the local search algorithms followed by nature. In practice, local search seems to efficiently find effective solutions. But practice is not theory.

As theorists, we can view combinatorial optimization problems as implicitly defining fitness landscapes that combine the numeric structure of the “fitness” function to be maximized with the combinatorial structure of which assignments are “adjacent” [1, 12, 32]. Since many local search algorithms stop at local peaks in these fitness landscapes, much work asks questions of effectiveness like “are these peaks ‘good enough’?” [1, 18]. Such questions of effectiveness can be avoided by focusing on just single-peaked fitness landscapes. Or even more stringently, by focusing on fitness landscapes on the hypercube of assignments that are single peaked on every subcube. These landscapes are known – depending on the research community – as semismooth fitness landscapes [30], completely unimodal pseudo-Boolean functions [21], or acyclic unique-sink orientations (AUSOs) of the hypercube [48, 50]. Semismooth fitness landscapes have a single peak, a short ascent from any starting point to this peak, and have nothing resembling other local peaks to potentially block local search (Propositions 3 and 4; Hammer et al. [21], Poelwijk et al. [44], and Kaznatcheev [30]; see Section 3). Local search is effective in finding the best possible result in semismooth landscapes, but can it do so efficiently?

The (in)efficiency of finding local peaks for general combinatorial optimization problems is captured by the complexity class of polynomial local search ($\mathrm{𝖯𝖫𝖲}$; [28]): if $\mathrm{𝖥𝖯}\ne \mathrm{𝖯𝖫𝖲}$ then there is no polynomial time algorithm (even non-local) that can find a local peak in general fitness landscapes. Many problems that generate these hard landscapes are complete under tight $\mathrm{𝖯𝖫𝖲}$-reductions, so have families of instances and initial assignments such that all ascents (i.e., sequences of adjacent assignments with strictly increasing fitness; Section 3) to any local peak are exponentially long [5, 28]. Thus, ascent-following local search will not find a local peak in polynomial time, even if $\mathrm{𝖥𝖯}=\mathrm{𝖯𝖫𝖲}$.²²2Restricting $\mathrm{𝖯𝖫𝖲}$-complete problems to a subset of instances that are tractable in polynomial time does not mean that particular local search algorithms will also find a peak in polynomial time. For example, $\mathrm{𝖶𝖾𝗂𝗀𝗁𝗍𝖾𝖽}\mathsf{\hspace{0.33em}2}\text{-}\mathrm{𝖲𝖠𝖳}$ is a $\mathrm{𝖯𝖫𝖲}$-complete problem [37, 46] and thus binary Boolean valued constraint satisfaction problems ($\mathrm{𝖵𝖢𝖲𝖯}$) are $\mathrm{𝖯𝖫𝖲}$-complete. For $\mathrm{𝖵𝖢𝖲𝖯}$-instances of bounded treewidth, the global peak can be found in polynomial time [4, 6]. Thus, bounded-treewdith $\mathrm{𝖵𝖢𝖲𝖯}$ is not $\mathrm{𝖯𝖫𝖲}$-complete. But exponentially long ascents exist (and greedy local search algorithms like $\mathrm{𝖲𝗍𝖾𝖾𝗉𝖾𝗌𝗍𝖠𝗌𝖼𝖾𝗇𝗍}$ can take exponentially long) even with binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$-instances of pathwidth 2 [32, 7, 33, 34, 51]. What is easy for non-local search is not necessarily easy for local search. In contrast, semismooth fitness landscapes always have some short ascent to their unique fitness peak. Thus, any results about (in)efficiency will have to be stated in terms of specific local search algorithms.³³3The special case of finding the peak in semismooth landscapes is reducible to $\mathrm{𝖴𝗇𝗂𝗊𝗎𝖾}\text{-}\mathrm{𝖤𝗇𝖽}\text{-}\mathrm{𝗈𝖿}$$\text{-}\mathrm{𝖯𝗈𝗍𝖾𝗇𝗍𝗂𝖺𝗅}\text{-}\mathrm{𝖫𝗂𝗇𝖾}$ – the complete problem for $\mathrm{𝖴𝖤𝖮𝖯𝖫}\subseteq \mathrm{𝖯𝖫𝖲}\cap \mathrm{𝖯𝖯𝖠𝖣}$ [15, 19]. It is believed that $\mathrm{𝖴𝖤𝖮𝖯𝖫}$ is strictly easier than $\mathrm{𝖯𝖫𝖲}$, but still not tractable in polynomial time. In a blackbox setting (no access to a concise description of the fitness landscape), $\mathrm{𝖴𝖤𝖮𝖯𝖫}$ and $\mathrm{𝖯𝖫𝖲}$ are not tractable in polynomial time. And there exist constructions of semismooth landscapes that cannot be solved efficiently by various popular local search algorithms including $\mathrm{𝖲𝗍𝖾𝖾𝗉𝖾𝗌𝗍𝖠𝗌𝖼𝖾𝗇𝗍}$ [13, 27, 30, 34], $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖠𝗌𝖼𝖾𝗇𝗍}$ [22, 39], $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖥𝖺𝖼𝖾𝗍}$ [17], jumping rules [47], and many others. It is generally believed that for any particular local search algorithm, there will be some family of semismooth fitness landscapes that show that the algorithm is not efficient. On semismooth fitness landscapes, even if local search is always effective, it is not always efficient.

This raises our main question for this paper: when is local search efficient on single-peaked landscapes? In a classic complexity theory setting, one wants to keep fixed a given problem (or class of problem instances) and seek for the simplest or most natural algorithm that solves this problem effectively (i.e., correctly) and efficiently (i.e., in polynomial time). We flip this formula around. We fix the algorithms and seek the most complex class of problem instances on which these algorithms can solve the problem effectively and efficiently. Specifically, we fix a collection of many popular local search algorithms and seek to find a large class of single-peaked fitness landscapes on which this collection of many local search algorithms is efficient (we abbreviate this as efficient-for-many; and we let our fixed collection be algorithms from a broader algorithm-class that we name poly-bypass).

Given that blackbox fitness landscapes are unwieldy exponentially large objects, we open the blackbox by representing fitness landscapes by instances of valued constraint satisfaction problems ($\mathrm{𝖵𝖢𝖲𝖯}$s) [32].⁴⁴4Our focus on easily checkable properties of polynomial-sized representations of problems instead of purely theoretical properties of the exponentially-large fitness landscapes implicit in the problems, is one of the big differences of our approach/results versus similar work in evolutionary computation [10, 12, 11]. Specifically, we study binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s, also known as quadratic pseudo-Boolean functions. Since arbitrary binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s are $\mathrm{𝖯𝖫𝖲}$-complete [5, 28, 37, 46], we will be looking for subclasses of binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s that implement single-peaked fitness landscapes on which poly-bypass local search algorithms can find the peak efficiently. Thus, our goal is to find an easy to check structural property of $\mathrm{𝖵𝖢𝖲𝖯}$s that captures the most expressive subclass of binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s for which many popular local search algorithms are both effective and efficient.

To avoid concerns over (in)effectiveness, we start Section 4 by identifying the binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s that implement semismooth fitness landscapes. We do this by assigning each edge in the constraint graph of a binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$ corresponding to a valued constraint between variable $x_i$ and $x_j$ one of two types: directed ($i\stackrel{}{\to }j$ or $j\stackrel{}{\to }i$) or bidirected ($i\stackrel{}{\leftrightarrow }j$). We show that $\mathrm{𝖵𝖢𝖲𝖯}$s without bidirectional edges are equivalent to semismooth fitness landscapes and name them directed $\mathrm{𝖵𝖢𝖲𝖯}$s. Given many constructions of hard semismooth fitness landscapes [13, 17, 22, 27, 30, 39, 47], we do not expect local search to be efficient on directed $\mathrm{𝖵𝖢𝖲𝖯}$s.

To find efficiency, we define oriented $\mathrm{𝖵𝖢𝖲𝖯}$s as a further restriction on directed $\mathrm{𝖵𝖢𝖲𝖯}$s. For each pair of variables $x_i$, $x_j$ in an oriented $\mathrm{𝖵𝖢𝖲𝖯}$ there can be at most one of $i\stackrel{}{\to }j$ or $j\stackrel{}{\to }i$: the constraint graph is oriented, hence the name. We show that there are no directed cycles in oriented $\mathrm{𝖵𝖢𝖲𝖯}$s: all oriented $\mathrm{𝖵𝖢𝖲𝖯}$s induce a partial order where the preferred assignment of a variable $x_j$ depends only on the assignments of variables $x_i$ with $i$ lower than $j$ in the partial order. This means that once we condition on all $x_i$ with $i$ lower than $j$, the preferred assignment of $x_j$ is independent of all other variables – like in a smooth landscape.

Although having a directed or oriented constraint graph is a natural property to define subclasses of $\mathrm{𝖵𝖢𝖲𝖯}$s, it is a hard property to recognize. Specifically, $\mathrm{𝖲𝗎𝖻𝗌𝖾𝗍𝖲𝗎𝗆}$ can be solved by determining the direction of constraints (Proposition B.1 for $i\stackrel{}{\leftrightarrow }j$ and Proposition B.2 for both $i\stackrel{}{\to }j$ and $j\stackrel{}{\to }i$). Thus, given an arbitrary binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$, the problem of checking if it is directed or oriented is $\mathrm{𝖼𝗈𝖭𝖯}$-complete (Corollary B.3). Furthermore, even if we are given a directed binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$, checking if it is oriented is $\mathrm{𝖼𝗈𝖭𝖯}$-complete (Corollary B.4). The only silver lining is that if we take the maximum degree of the constraint graph of the $\mathrm{𝖵𝖢𝖲𝖯}$-instance as a parameter then checking if a binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$ is directed or oriented is fixed-parameter tractable (Algorithm 2 and Appendix B.2).

Given the importance of the partial order of conditional independence but the difficulty of recognizing if a $\mathrm{𝖵𝖢𝖲𝖯}$ is oriented, with Footnote˜8 in Section 5, we abstract to a class of landscapes that we call conditionally-smooth. Just like smooth and semismooth landscapes, conditionally-smooth landscapes have only one local (and thus global) peak and there exist short ascents from any initial assignment to the peak (Proposition 9). In other words, just as with semismooth landscapes, local search algorithms are effective on conditionally-smooth landscapes. Unlike directed or oriented $\mathrm{𝖵𝖢𝖲𝖯}$s, however, we show how to recognize if an arbitrary binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$ is conditionally-smooth in polynomial time (Algorithm 3).

In Section 6, we show that – unlike general semismooth fitness landscapes (and like smooth landscapes and oriented $\mathrm{𝖵𝖢𝖲𝖯}$s) – conditionally-smooth fitness landscapes are not just effective-for but also efficient-for-many local search algorithms.⁵⁵5We do not focus on efficient-for-all (or more formally: landscapes where all ascents are polynomial length) because we think that this case is too strict and has been largely resolved. Kaznatcheev, Cohen and Jeavons [32] showed that all ascents have length $\le \left(\genfrac{}{}{0pt}{}{n+1}{2}\right)$ in fitness landscapes that are implementable by binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$ with tree-structured constraint graphs. Efficient-for-all cannot be pushed much further than Boolean trees: Kaznatcheev, Cohen and Jeavons [32] also gave examples of $\mathrm{𝖵𝖢𝖲𝖯}$s with exponential ascents from (a) domains of size $\ge 3$ and path-structured constraint graphs, or (b) Boolean domains and constraint graphs of pathwidth $2$. This is why, we switch from the question of efficient-for-all to the question of efficient-for-many. Specifically, we show that conditionally-smooth fitness landscapes are solved efficiently by many local search algorithms including $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖠𝗌𝖼𝖾𝗇𝗍}$ (Proposition 14); $\mathrm{𝖲𝗁𝖺𝗄𝖾𝗇𝖠𝗌𝖼𝖾𝗇𝗍}$ (Proposition C.2); $\mathrm{𝖲𝗂𝗆𝗎𝗅𝖺𝗍𝖾𝖽𝖠𝗇𝗇𝖾𝖺𝗅𝗂𝗇𝗀}$ (Proposition 15); $\mathrm{𝖹𝖺𝖽𝖾𝗁𝗌𝖱𝗎𝗅𝖾}$, $\mathrm{𝖫𝖾𝖺𝗌𝗍𝖱𝖾𝖼𝖾𝗇𝗍𝗅𝗒𝖢𝗈𝗇𝗌𝗂𝖽𝖾𝗋𝖾𝖽}$, and other history-based local search (Proposition C.6); $\mathrm{𝖠𝗇𝗍𝗂𝗉𝗈𝖽𝖺𝗅𝖩𝗎𝗆𝗉}$ and $\mathrm{𝖩𝗎𝗆𝗉𝖳𝗈𝖡𝖾𝗌𝗍}$ (Proposition C.8); $\mathrm{𝖪𝖾𝗋𝗇𝗂𝗇𝗀𝗁𝖺𝗇𝖫𝗂𝗇}$ (Proposition C.10); and $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖩𝗎𝗆𝗉}$ (Proposition 16) – all of these are examples a broader class of local search algorithms that we name poly-bypass local search algorithms (Footnote˜9). Conditionally-smooth landscapes are a more expressive class than the tree-structured binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s that (fully) capture the class of fitness landscapes that are efficient-for-all local search algorithms [32]. Thus, the conditionally-smooth structural property permits families of landscapes that are complex enough to break the efficiency of some popular local search algorithms that are not poly-bypass algorithms. In Section 7, we show that there are families of conditionally-smooth landscapes where finding the peak takes an exponential number of steps for $\mathrm{𝖲𝗍𝖾𝖾𝗉𝖾𝗌𝗍𝖠𝗌𝖼𝖾𝗇𝗍}$ (Theorem 19) and takes a superpolynomial number of steps for $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖥𝖺𝖼𝖾𝗍}$ (Theorem 23). Given that both $\mathrm{𝖲𝗍𝖾𝖾𝗉𝖾𝗌𝗍𝖠𝗌𝖼𝖾𝗇𝗍}$ and $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖥𝖺𝖼𝖾𝗍}$ [17] are often considered to be very good local search algorithms,⁶⁶6$\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖥𝖺𝖼𝖾𝗍}$ is currently considered the best known algorithm for solving semismooth fitness landscapes. It finds the peak in any semismooth fitness landscapes in a superpolynomial but subexponential number of steps – even with the landscape given as a black-box [17]. In Corollary 22, we show that the family of semismooth landscapes that saturate this worst case behavior for $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖥𝖺𝖼𝖾𝗍}$ are conditionally-smooth. their inefficiency on conditionally-smooth landscapes tells us that conditionally-smooth landscapes are not a trivially easy to solve class of landscapes.

We consider assignments $x\in {\{0,1\}}^n$ from the $n$-dimensional hypercube where $x_i$ refers to the $i$-th entry of $x$. To refer to a substring with indexes $S\subseteq [n]$, we will write the partial assignment $y=x[S]\in {\{0,1\}}^S$. If we want to modify a substring with indexes $S\subseteq [n]$ to match a partial assignment $y\in {\{0,1\}}^S$ (or any string $y\in {\{0,1\}}^{|S|}$), we write $x[S\mapsto y]$. We abbreviate $x[\{i\}\mapsto b]$ by just $x[i\mapsto b]$. Two assignments are adjacent if they differ on a single bit: $x,y\in {\{0,1\}}^n$ are adjacent if there exists an index $i\in [n]$ such that $y=x[i\mapsto {\overline{x}}_i]$, where ${\overline{x}}_i:=1-x_i$ is the negation of $x_i$.

This combinatorial structure of adjacent assignments can be combined with the numeric structure of a pseudo-Boolean function (that we call the fitness function) to create a fitness landscape [54, 30, 32]. A fitness landscapes $f$ associates to each assignment $x$ the integer $f(x)$ and a set of adjacent assignments. Given an assignment $x$, we let ${\varphi }^{+}(x)=\{i|i\in [n]\text{ and }f(x[i\mapsto {\overline{x}}_i])>f(x)\}$ be the indexes of variables that increase fitness when flipped (out-map) and ${\varphi }^{-}(x)=\{i|i\in [n]\text{ and }f(x)\ge f(x[i\mapsto {\overline{x}}_i])\}$ be the set of indexes that lower or do not increase fitness when flipped (in-map). An assignment $x$ is a local peak in $f$ if for all $y$ adjacent to $x$ we have $f(x)\ge f(y)$ (i.e., if ${\varphi }^{+}(x)$ is empty).⁷⁷7Note that local peaks are not necessarily “strict”, they can have adjacent assignments of equal (but not greater) fitness. So what some call a “fitness plateau” is for us a collection of adjacent local peaks. This transforms how we think about popular “hard” landscapes like $\mathrm{𝖭𝖾𝖾𝖽𝗅𝖾}$ from the evolutionary computation literature. A landscape $f$ is a $\mathrm{𝖭𝖾𝖾𝖽𝗅𝖾}$ landscape if there exists a single assignment $x^{\text{needle}}$ such that $f(x^{\text{needle}})=1$ and for all other assignments $x\ne x^{\text{needle}}f(x)=0$. We use the scare quotes around hard because for our definition of local peaks, $\mathrm{𝖭𝖾𝖾𝖽𝗅𝖾}$ landscapes are trivial: every assignment is either a local peak (for $x^{\text{needle}}$ and any $x\ne x^{\text{needle}}$ not directly adjacent to $x^{\text{needle}}$) or directly adjacent to a local peak (for $y$ directly adjacent to $x^{\text{needle}}$) and are thus solved by any local search algorithm in at most one step. $\mathrm{𝖭𝖾𝖾𝖽𝗅𝖾}$ landscapes are only hard if we are looking for a global peak instead of any local peak. So from the perspective of our effective vs efficient distinction, many intractability results that rely on the difficulty of ‘navigating fitness plateaus or crossing fitness valleys’ are statement of ineffectiveness rather than inefficiency. This is one of the big differences between our approach and results, and the approach and results in the evolutionary computation literature [52, 25, 10, 12, 11, 23]. A sequence of assignments $x^0,x^1,\mathrm{\dots },x^T$ is an ascent if every $x^{t-1}$ and $x^t$ are adjacent with the latter having higher fitness (i.e., $\forall t\le T{x}^t=x^{t-1}[i\mapsto \overline{x_i^{t-1}}]\text{ and }i\in {\varphi }^{+}(x^{t-1})$) and $x^T$ is a local peak.

A fitness landscape $f$ is smooth if for each $i\in [n]$ there exists an assignment $x_i^{\ast }$ such that for all assignments $x$ we have $f(x[i\mapsto x_i^{\ast }])>f(x[i\mapsto \overline{x_i^{\ast }}])$. In other words, in a smooth landscape, each variable $x_i$ has a preferred assignment $x_i^{\ast }$ that is independent of how other variables are assigned. It is easy to see that all ascents are short (i.e, $\le n$) in smooth fitness landscapes, so smooth landscapes are effective- and efficient-for-all local search algorithms.

We can relax the definition of smooth while maintaining effectiveness: a fitness landscape on the hypercube is a semismooth fitness landscape if every subcube is single peaked [30]. These are also known as completely unimodal pseudo-Boolean functions [21], or acyclic unique-sink orientations (AUSOs) of the hypercube [48, 50]. Semismooth fitness landscapes have a nice characterization in terms of the biological concept of sign epistasis [30, 44, 43, 53]:

This terminology of “sign” comes from the observation that the sign of the fitness effect of a change in $x_i$ depends on the value of $x_j$. Since the sign of the fitness effect of a change in $x_i$ just indicates the preferred assignment of $x_i$ (with a positive sign indicating $x_i^{\ast }=1$ and negative indicating $x_i^{\ast }=0$), it is easy to link this definition to smooth landscapes: a smooth landscape is a fitness landscapes where all indexes are sign-independent. Or stated in the negative, a smooth landscape is one without sign-dependence. We will relax this negative definition to get semismooth landscapes by instead excluding the concept of “reciprocal sign epistasis” [43, 44]:

If the background $x$ is clear form context or not important then we drop the superscript in the above notations and just write $j\stackrel{}{\to }i$ or $i\stackrel{}{\leftrightarrow }j$. The absence of reciprocal sign epistasis is clearly necessary for a fitness landscape to be semismooth, but it is also sufficient:

Conveniently, semismooth landscapes always have a short ascent to the unique peak:

Unlike smooth landscapes, however, not all ascents in semismooth fitness landscapes are short, and finding and following a short ascent is not easy. The Klee-Minty cube [36] is a construction of a semismooth fitness landscape on ${\{0,1\}}^n$ with an ascent of length $2^n-1$. As for local search algorithms, constructions exists such that semismooth landscapes are not tractable in polynomial time by various popular ascent-following local search algorithms including $\mathrm{𝖲𝗍𝖾𝖾𝗉𝖾𝗌𝗍𝖠𝗌𝖼𝖾𝗇𝗍}$ [13, 27, 30], $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖠𝗌𝖼𝖾𝗇𝗍}$ [22, 39], $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖥𝖺𝖼𝖾𝗍}$ [17], jumping rules [47], and many others. Thus, local search is not efficient on all semismooth fitness landscapes. So we start our search for single-peaked landscapes that are efficient-for-many local search algorithms by looking for natural subclasses of semismooth fitness landscapes.

As blackboxes, fitness landscapes are unwieldy exponentially large objects, so we open the blackbox by representing landscapes by instances of valued constraint satisfaction problems ($\mathrm{𝖵𝖢𝖲𝖯}$s) [32]. We can then find which natural subclass of $\mathrm{𝖵𝖢𝖲𝖯}$s represents semismooth fitness landscapes along with an algorithms for checking when a given $\mathrm{𝖵𝖢𝖲𝖯}$-instance has these properties. A Boolean $\mathrm{𝖵𝖢𝖲𝖯}$-instance is a set of constraint weights $𝒞=\{c_S\}$ where each weight $c_S\in \mathbb{Z}\setminus \{0\}$ has a scope $S\subseteq [n]$. This set of constraints implements a pseudo-Boolean function:

If $|S|\le 2$ for all constraints then we say the $\mathrm{𝖵𝖢𝖲𝖯}$ is binary. We also view every binary $\mathrm{𝖵𝖢𝖲𝖯}$-instance $𝒞$ as a constraint graph with edges $\{i,j\}\in E(𝒞)$ if $c_{ij}:=c_{\{i,j\}}\in 𝒞$ and a neighbourhood function $N_{𝒞}(i)=\{j|\{i,j\}\in E(𝒞)\}$. This constraint graph is a way of representing where the potential sign-dependencies are in the fitness landscape.

Given a binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$ $𝒞$ on the whole $n$-dimensional hypercube, it is sometimes useful to consider the binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$ ${𝒞}^{\prime }$ restricted to just a subset of the indexes $R\subseteq [n]$ with the other variables in $S:=[n]\setminus R$ fixed to some assignment $y\in {\{0,1\}}^S$ (i.e., restricted to the face ${\{0,1\}}^{R}y$). This restricted $\mathrm{𝖵𝖢𝖲𝖯}$ ${𝒞}^{\prime }$ will have the same binary constraint as $𝒞$ (i.e., if $i,j\in R$ and $c_{ij}\in 𝒞$ then $c_{ij}\in {𝒞}^{\prime }$) but the unary constraints will change to what we call the effective unaries that “absorb” the binary constraints that cross the $R$-$S$ cut:

If $x$ and $y$ are two assignments with $x[N(i)\setminus R]=y[N(i)\setminus R]$ then ${\widehat{c}}_i(x,R)={\widehat{c}}_i(y,R)$. We use this to overload ${\widehat{c}}_i$ to partial assignments: given $T\supseteq N(i)\setminus R$ and $y\in {\{0,1\}}^T$, we interpret ${\widehat{c}}_i(y,R)$ as ${\widehat{c}}_i(y{0}^{[n]\setminus T},R)$. From this, it is easy to see that restricting our $\mathrm{𝖵𝖢𝖲𝖯}$ $𝒞$ to $𝒞$’ on the face ${\{0,1\}}^{R}y$ will change the unaries to $c_i^{\prime }={\widehat{c}}_i(y,R)$ (for $i\in R$).

In terms of representation of smooth landscapes, it is clear than if all constraints in a $\mathrm{𝖵𝖢𝖲𝖯}$ are unary then the resulting fitness landscape is smooth. But even given a binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$-instance with non-unary constraints, it is easy to check if that $\mathrm{𝖵𝖢𝖲𝖯}$-instance implements a smooth landscape by checking if the unary constraints are “sufficiently large” compared to the relevant binary constraints. Or more generally, given any partial assignment $y\in {\{0,1\}}^S$ it is easy to check if the face ${\{0,1\}}^{[n]-S}y$ is smooth using the effective unaries. We will do this check one variable at a time. For a variable $x_i$ to have a preferred assignment that is independent of how other variables are assigned, its unary must dominate over the binary constraints that it participates in – its unary must have big magnitude. For example, suppose that $c_i>0$ then $x_i$ will prefer to be $1$ if all of its neighbours are $0$. This preference must not change as any $x_j$ with $j\in N(i)$ change to $1$s. Since $x_j$ with are the only ones that can lower $x_i$’s preference for $1$, this becomes equivalent to checking if . There exists a combination of $x_j$s that flip $x_i$’s preference if and only if this inequality is violated. In moving from this particular example to the general case, we can also generalize our algorithm to check not only if $x_i$ has an independent preference in the whole landscape but also if it has a conditionally independent preference conditional on some variables with indexes $j\in S$ not being able to vary and fixed to some $y\in {\{0,1\}}^S$. To do this we only need to replace $c_i$ by the effective unary of Definition 5 ${\widehat{c}}_i={\widehat{c}}_i(y,N(i)\setminus S):=c_i+{\sum }_{j\in S\cap N(i)}{y}_j{c}_{ij}$ and consider $c_{ij}$s with $\text{sgn}({\widehat{c}}_i)\ne \text{sgn}(c_{ij})$ and $j\in N(i)\setminus S$. We encode this in $\mathrm{𝖢𝗈𝗇𝖽𝗂𝗍𝗂𝗈𝗇𝖺𝗅𝗅𝗒𝖲𝗂𝗀𝗇𝖨𝗇𝖽𝖾𝗉𝖾𝗇𝖽𝖾𝗇𝗍}$$(𝒞,i,S,y)$ of Algorithm 1.

Given a binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$-instance $𝒞$, this algorithms runs in time linear in the maximum degree $\mathrm{\Delta }(𝒞)$ of the constraint graph. To check if $𝒞$ implements a smooth landscape, run $\mathrm{𝖢𝗈𝗇𝖽𝗂𝗍𝗂𝗈𝗇𝖺𝗅𝗅𝗒𝖲𝗂𝗀𝗇𝖨𝗇𝖽𝖾𝗉𝖾𝗇𝖽𝖾𝗇𝗍}$$(𝒞,i,\mathrm{\varnothing },0^n)$ on every $i$ and return the conjunction of their outputs in $O(\mathrm{\Delta }(𝒞)n)$ time.

Now let us return to view the constraint graph as a way of represetning where the potential sign-dependencies are in a fitness landscape. If $\mathrm{𝖵𝖢𝖲𝖯}$-instance with binary constraints is smooth then this tells us that the edges in the constraint-graph did not actually encode any actual sign-dependence. This idea can be taken further by converting edges to arcs and assigning “directions” to the binary constraint $c_{ij}$ based on how its weight compares to the effective unaries ${\widehat{c}}_i$ across various background assignments (see Figure 1 for illustration):

From this, each edge $\{i,j\}\in E(𝒞)$ is assigned only one of the three kinds of arcs: $\{i\leftrightarrow j\}$ or $\{i\to j$ and/or $i\leftarrow j\}$ or $\{\}$. In Figure 1, we provide some minimal prototypical examples of $\mathrm{𝖵𝖢𝖲𝖯}$-instances that have (a) no direction for the constraint with scope $\{i,j\}$, (b) $i\to j\in A(𝒞)$, (c) both $i\to j,i\leftarrow j\in A(𝒞)$, or (d) $i\leftrightarrow j\in A(𝒞)$. Most of these examples are on two variables. Since it is impossible to have both both $i\to j$ and $i\leftarrow j$ without a $k\in N(i)\cup N(j)$ (Proposition A.4), the minimal instance in Figure 1(c) requires three variables. It is easy to check that the overloading of the sign-dependence and reciprocal sign epistasis symbols is appropriate. Most importantly, the fitness landscape will have reciprocal sign epistasis if and only if the $\mathrm{𝖵𝖢𝖲𝖯}$-instance $𝒞$ implementing it has $\{i\leftrightarrow j\}\in A(𝒞)$.

The advantage of Definition 6 over black-box features of the fitness landscape is its statement in terms of properties of just the $\mathrm{𝖵𝖢𝖲𝖯}$-instance. This means, for example, that if we want to check the potential direction of a constraint with scope $\{i,j\}\in E(𝒞)$ with then we need to compare it to the effective unaries ${\widehat{c}}_i(x,\{i,j\})$ and ${\widehat{c}}_j(x,\{i,j\})$ for various choices of $x$. If we find an $x$ such that both $|c_{ij}|>{\widehat{c}}_i(x,\{i,j\})>0$ and $|c_{ij}|>{\widehat{c}}_j(x,\{i,j\})>0$ are simultaneously satisfied then we output that $i\leftrightarrow j\in A(𝒞)$. If we only ever satisfy one or fewer of these equations for all choices of $x$ then we need to output a subset of $\{i\to j,i\leftarrow j\}$ depending on which of the comparisons was true. Outputing $\{\}$ if neither comparison was ever satisfied, $i\to j$ if only the first was satisfied, $i\leftarrow j$ if only the second, and $\{i\to j,i\leftarrow j\}$ if each was true in a different background. Finally, to be fixed-parameter tractable, it is important to use that ${\widehat{c}}_i(x,R)={\widehat{c}}_i(y,R)$ when $x[N(i)\setminus R]=y[N(i)\setminus R]$ to limit our search to just partial assignments $x\in {\{0,1\}}^{N(i)\cup N(j)\setminus \{i,j\}}.$ We formalize this as Algorithm 2:

The resulting worst-case runtime is $2^{O(\mathrm{\Delta }(𝒞))}$, or an overall runtime of $2^{O(\mathrm{\Delta }(𝒞))}O(\mathrm{\Delta }(𝒞)n)$ to determine the direction of all arcs in the $\mathrm{𝖵𝖢𝖲𝖯}$-instance $𝒞$. This is fixed-parameter tractable when parameterized by the maximum number of constraints incident on a variable ($\mathrm{\Delta }(𝒞)$). A fully polynomial time algorithm for finding arc directions is unlikely given that the questions “is $i\stackrel{}{\leftrightarrow }j\in A(𝒞)$?” (Proposition B.1) and “are both $i\stackrel{}{\to }j$ and $j\stackrel{}{\to }i$ in $A(𝒞)$?” (Proposition B.2) are $\mathrm{𝖭𝖯}$-complete by reduction from $\mathrm{𝖲𝗎𝖻𝗌𝖾𝗍𝖲𝗎𝗆}$. However, we can still define two natural subclasses of $\mathrm{𝖵𝖢𝖲𝖯}$s by restricting the bidirected constraint graph:

In Appendix A, we extend Proposition 3 to representations to show that a quadratic pseudo-Boolean $f$ is semismooth if and only if the corresponding $\mathrm{𝖵𝖢𝖲𝖯}$ is directed (Proposition A.1), any triangle-free directed $\mathrm{𝖵𝖢𝖲𝖯}$ is oriented (Theorem A.3), and oriented $\mathrm{𝖵𝖢𝖲𝖯}$s are always acyclic (Proposition A.5). Theorem A.3 and Proposition A.5 let us view oriented $\mathrm{𝖵𝖢𝖲𝖯}$s as a kind of generalization of the tree-structured $\mathrm{𝖵𝖢𝖲𝖯}$s that Kaznatcheev, Cohen, and Jeavons [32] showed are efficient-for-all local search algorithms. Specifically, we replace the undirected acyclicity of trees by the directed acyclicity of DAGs. Unfortunately, checking if a $\mathrm{𝖵𝖢𝖲𝖯}$ is directed or oriented is $\mathrm{𝖼𝗈𝖭𝖯}$-complete (Corollary B.3 and Corollary B.4).

One of these nice features of our two natural subclasses of directed and oriented $\mathrm{𝖵𝖢𝖲𝖯}$s is that they let us capture when fitness landscapes are both effective-for-all and efficient-for-many local search algorithms. Directed $\mathrm{𝖵𝖢𝖲𝖯}$s capture the semismooth fitness landscapes that are effective-for-all local search algorithms, but that have no known efficient algorithms. Oriented $\mathrm{𝖵𝖢𝖲𝖯}$s are then a further restriction to capture those semismooth fitness landscapes that are efficient-for-many local search algorithms. By focusing on the main aspect of acyclicity that makes oriented $\mathrm{𝖵𝖢𝖲𝖯}$ tractable, we can generalize that class to a slightly larger class of conditionally-smooth fitness landscapes that are also single-peaked (and so effictive-for-all local search algorithms) but also recognizable from the implementing $\mathrm{𝖵𝖢𝖲𝖯}$-instance.

The acyclicity of an oriented $\mathrm{𝖵𝖢𝖲𝖯}$-instance (Proposition A.5) lets us define a strict partial order $\prec$ as the transitive closure of the constraint graph and the corresponding down sets $\downarrow j=\{i|i\prec j\}$. As we show later, what makes oriented $\mathrm{𝖵𝖢𝖲𝖯}$s efficient for many local search algorithms is that this order respects conditional independence (from Algorithm 1). Specifically Proposition A.7: for oriented $\mathrm{𝖵𝖢𝖲𝖯}$-instance $𝒞$, $\forall y\in {\{0,1\}}^{\downarrow j}$ $\mathrm{𝖢𝗈𝗇𝖽𝗂𝗍𝗂𝗈𝗇𝖺𝗅𝗅𝗒𝖲𝗂𝗀𝗇𝖨𝗇𝖽𝖾𝗉𝖾𝗇𝖽𝖾𝗇𝗍}(𝒞,j,\downarrow j,y)=\text{True}$. Proposition A.7 is a powerful defining feature of oriented $\mathrm{𝖵𝖢𝖲𝖯}$s, but it is more powerful (and restrictive) than necessary for efficiency. To get our definition of the larger class of conditionally-smooth fitness landscapes, we can relax from conditional sign independence for any background $y\in {\{0,1\}}^{\downarrow j}$ to just a single background $y=x^{\ast }[\downarrow j]$ where $x^{\ast }$ is the peak of a single-peaked landscape:

Conditionally-smooth landscapes generalize both oriented $\mathrm{𝖵𝖢𝖲𝖯}$s and recursively combed AUSOs (Definition A.8). Although conditionally-smooth landscapes are not always semismooth, they are singled peaked and have direct ascents from any assignment to the peak:

Local search starts at some initial assignment $x^0$ and takes steps to assignments $x^1,x^2,\mathrm{\dots },x^T$ with $x^T$ as a local peak. If, additionally, for every we have $f(x^{t+1})>f(x^t)$ then local search followed an ascent. For an arbitrary local search algorithm $𝖠$ we let ${𝖠}_f^t(x)$ denote $t$ steps of $𝖠$ from $x$ on fitness landscape $f$.

For a $p(n)$-bypass algorithm, any index $i$ that could have flipped to increase fitness at some step $s$ (i.e., $i\in \varphi (x^s)$), will become an index that cannot be flipped to increase fitness at some point in the subsequent $p(n)$ steps. This can happen either because the variable with index $i$ flips or because some other indexes flip in a way that makes a flip at $i$ no longer fitness increasing. In other words, no potential fitness-increasing flip was bypassed for more than $p(n)$ steps. Hence, the name.

Now, we can easily show that conditionally-smooth landscapes are efficient for $p(n)$-bypass local search algorithms.

Finally, in this section, we want to argue that the effectiveness of many local search algorithms on conditionally-smooth landscapes is not a trivial observation. We do this by showing that conditionality-smooth landscapes are not tractable for some algorithms that are often considered to be very good local search algorithms (but that happen to not be poly-bypass). Specifically, we will show that oriented $\mathrm{𝖵𝖢𝖲𝖯}$s can represent families of landscapes where $\mathrm{𝖲𝗍𝖾𝖾𝗉𝖾𝗌𝗍𝖠𝗌𝖼𝖾𝗇𝗍}$ takes an exponential number of steps; and that conditionally-smooth landscapes include families of semismooth landscapes where $\mathrm{𝖱𝖺𝗇𝖽𝗈𝗆𝖥𝖺𝖼𝖾𝗍}$ takes a superpolynomial number of steps. In other words, conditionally-smooth landscapes are expressive enough to contain very complicated kinds of fitness landscapes.

While studying Hopfield networks, Haken and Luby [20] created a family of binary Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s with exponentially long steepest ascents. Here we show that the Haken-Luby $\mathrm{𝖵𝖢𝖲𝖯}$ is oriented and has pathwidth $3$. The Haken-Luby $\mathrm{𝖵𝖢𝖲𝖯}$ has variables with indexes $\{(k,i)|k\in [n],i\in [7]\}$ where each set of seven variables $\{(k,1),(k,2),\mathrm{\dots }(k,7)\}$ forms a gadget. The gadgets form a chain by connecting $(k,7)$ to $(k-1,1)$. The magnitude of the constraints on the $k$th module is roughly proportional to $M_k=\frac{5}{6}(6^k-6)$ and the exact constraints, with the exception of $c_{(n,1)}=(6M_n+24)K$, where $K=2n+1$ is constant for the instance, are given by Figure 2. For example, $c_{(k,5),(k,7)}=-(2M_k+4)K$ and $c_{(k,7),(k-1,1)}=M_{k}K$. In Figure 2 we also included the direction of the constraints.

Overall, we showed that conditionally-smooth fitness landscapes – a polynomial-time testable structural property of $\mathrm{𝖵𝖢𝖲𝖯}$s that generalizes the natural notion of oriented $\mathrm{𝖵𝖢𝖲𝖯}$s – are an expressive subclass of Boolean $\mathrm{𝖵𝖢𝖲𝖯}$s for which many (but not all) popular local search algorithm are both effective and efficient. Future work could further generalize conditionally-smooth landscapes from Boolean to higher-valence domains. This might allow us to engage with directed $\mathrm{𝖵𝖢𝖲𝖯}$s where each strongly connected component is of small size $D\in O(\log n)$ by modeling the whole connected component as one domain with $2^D$ values. Would this class still be efficient-for-many local search algorithms? Is local search fixed-parameter tractable when parameterized by the size of the $\mathrm{𝖵𝖢𝖲𝖯}$’s largest strongly connected component?

We hope that our results on conditionally-smooth fitness landscapes contribute to a fuller understanding of when local search is both effective and efficient. This is interesting for theory as it grows our understanding of parameterized complexity, especially for $\mathrm{𝖯𝖫𝖲}$. This theory can guide us to what properties practical fitness landscapes might have in the real-world cases where local search seems to work well. Finally, we are excited about the use of these results for theory-building in the natural sciences. When local search is used by nature, we often do not have perfect understanding of which local search algorithm nature follows. But we might have strong beliefs about nature’s algorithm being efficient. In this case, a good understanding of what landscapes are efficient-for-many local search algorithms can help us to reduce the set of fitness landscapes that we consider theoretically possible in nature. This can be especially useful in fields like evolutionary biology [30, 31] and economics [45] where we have only limited empirical measurements of nature’s fitness landscapes.