Computational Complexity of Simultaneous Elementary Matching Problems

The simultaneous elementary E-matching problem for an equational theory E is to decide whether there is an E-matcher for a given system of equations in which the only nonconstant function symbols occurring in the terms to be matched are the ones constrained by the equational axioms of E. We study the computational complexity of simultaneous elementary matching problems for the equational theories A of semigroups, AC of commutative semigroups, and ACU of commutative monoids. In each case, we delineate the boundary between NP-completeness and solvability in polynomial time by considering two parameters, the number of equations in the systems and the number of constant symbols in the signature. Moreover, we analyze further the intractable cases of simultaneous elementary AC-matching and ACU-matching by also taking into account the maximum number of occurrences of each variable. Using combinatorial optimization techniques, we show that if each variable is restricted to having at most two occurrences, then several cases of simultaneous elementary AC-matching and ACU-matching can be solved in polynomial time.     

Performance of a ventilated-façade system under fire conditions: An experimental investigation

During a fire event, ventilated facade systems may contribute to external fire spreading to the upper floors of a building via the facade, thus representing a significant risk. In this frame, the performance of a typical ventilated façade system under fire conditions is experimentally investigated, using a full-scale compartment-facade test rig. Two alternative façade configurations are examined and comparatively assessed, namely a plain façade (PF) and a ventilated façade (VF) system. Emphasis is given on the estimation of the thermal characteristics of the developed Externally Venting Flames (EVF) and the thermal boundary conditions developing on the façade's exposed surface. An extensive set of sensors was installed at the interior of the fire compartment, the façade systems and the exterior of the test configurations. Analysis of the experimental data suggests that even though gaseous combustion products managed to penetrate the air cavity of the VF system, no consistent flaming conditions were established. On the unexposed face of both PF and VF systems, temperatures remained constantly below 180°C throughout the duration of both fire tests. The Eurocode correlations are assessed against the obtained experimental data; certain parameters, such as EVF length, width and centreline temperature, are found to be under-estimated by the Eurocode methodology.     

Subtractive reductions and complete problems for counting complexity classes

We introduce and investigate a new type of reductions between counting problems, which we call subtractive reductions. We show that the main counting complexity classes #P, #NP, as well as all higher counting complexity classes $\#·{\Pi }_k\mathrm{P},k⩾2$, are closed under subtractive reductions. We then pursue problems that are complete for these classes via subtractive reductions. We focus on the class #NP (which is the same as the class $\#·\mathrm{coNP}$) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a Boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear Diophantine inequalities.