On the applicability of Postʼs lattice

For decision problems $\Pi (B)$ defined over Boolean circuits using gates from a restricted set B only, we have $\Pi (B){?}_m^{{\mathrm{AC}}^0}\Pi (B^{\prime })$ for all finite sets B and $B^{\prime }$ of gates such that all gates from B can be computed by circuits over gates from $B^{\prime }$. In this note, we show that a weaker version of this statement holds for decision problems defined over Boolean formulae, namely that $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{\wedge ,\vee \})$ and $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{0,1\})$ for all finite sets B and $B^{\prime }$ of Boolean functions such that all $f\in B$ can be defined in $B^{\prime }$.     

Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges

Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to $2\lfloor \frac{n(G)}{2}\rfloor$, where $n(G)$ is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to $n(G)$, where $r\ge 3$. A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where $n(G)$, $n(H)\ge$ 9, let $k_1$, $k_2\ge 5$ be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph $G\times H$ with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of ${\mathit{NQ}}_{m_r,\dots ,m_1}$ and ${\mathit{GQ}}_{m_r,\dots ,m_1}$.     

Equations over sets of integers with addition only

Systems of equations of the form $X=Y+Z$ and $X=C$ are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set $S\subseteq \mathbb{N}$ there exists a system with a unique (least, greatest) solution containing a component T with $S=\{n|16n+13\in T\}$. Testing solution existence for these equations is ${\mathrm{\Pi }}_1^0$-complete, solution uniqueness is ${\mathrm{\Pi }}_2^0$-complete, and finiteness of the set of solutions is ${\mathrm{\Sigma }}_3^0$-complete. A similar construction for integers represents any hyper-arithmetical set $S\subseteq \mathbb{Z}$ by a set $T\subseteq \mathbb{Z}$ satisfying $S=\{n|16n\in T\}$, whereas testing solution existence is ${\mathrm{\Sigma }}_1^1$-complete.     

Pancyclic out-arcs of a vertex in oriented graphs

Let D be an oriented graph with $n?9$ vertices and minimum degree at least $n?2$, such that, for any two vertices x and y, either x dominates y or $d_D^{+}(x)+d_D^{?}(y)?n?3$. Song (1994) [5] proved that D is pancyclic. Bang-Jensen and Guo (1999) [2] proved, based on Song?s result, that D is vertex pancyclic. In this article, we give a sufficient condition for D to contain a vertex whose out-arcs are pancyclic in D, when $n?14$.