In recent years, computational models have been increasingly used in cell signaling research and have been developed to study various pathways. 3, showing membership in P would require breakthroughs that currently (and likely over the next decades) seem out of reach, and would moreover break some public key cryptographic systems.In computational systems biology, studying a complex biochemical system involving a large number of interacting proteins often relies on in silico simulations to analyze and predict system behaviors. Is existential Büchi arithmetic with a fixed number of variables (and possibly even a fixed number of literals) NP-complete? As discussed in Sect.
However, the author is not aware of a quantifier-elimination procedure for Büchi arithmetic that given a formula of Büchi arithmetic allows for obtaining an equivalent formula of existential Büchi arithmetic.
4 that this is the case for existential Büchi arithmetic. Is Büchi arithmetic with valuation constraints decidable? It can be derived from the approach presented in Sect. Generally speaking, what are natural applications of Presburger arithmetic with valuation constraints? Decidability in such contexts is rare, and NP-completeness of its existential fragment means that this logic could potentially find practical applications in areas such as formal verification, as we seemingly can, for instance, express some problems typically arising in bit-vector arithmetic. Presburger arithmetic with valuation constraints is a powerful logic which can be used to reason about sets of integers which are not semi-linear. 2 Looking at the similarities of the definitions of \(X_p(x,u,k)\) and \(V_p\), it seems conceivable that existential BRW arithmetic is also NP-complete, though this is likely more tedious to prove mainly because some real numbers have multiple encodings (e.g., \(1.0000\cdots = 0.9999\cdots \)). We denote by \(\mathbb _+,0,1,+,X_p \rangle \) ( BRW arithmetic after the authors of for short). We conclude with some observations and discussion of open problems. Those results are somewhat implicit in but seem worthwhile being explicated in written. We subsequently show how the techniques used for the NP upper bound can be applied in order to show decidability and complexity results for an extension of Presburger arithmetic with valuation constraints. This article gives a high-level yet sufficiently detailed outline of how the NP upper bound for existential Büchi arithmetic can be obtained. The key result underlying both NP upper bounds is that given two states of a finite-state automaton encoding the set of solutions of a system of linear Diophantine equations, one can decide whether one state reaches the other in NP in the size of the encoding of the system (and without explicitly constructing the automaton). The NP upper bounds are the non-trivial part in those results, since, unlike, for instance, in existential Presburger arithmetic, the encoding of smallest solutions can grow super-polynomially. The author’s opinion drastically changed when appealing to automata-based approaches recently allowed for settling long-standing open problems about the complexity of the existential fragments of Büchi arithmetic and linear arithmetic over p-adic fields, which were both shown NP-complete . Given this history, it is not surprising that, until recently, the author was of the opinion that automata should better be avoided when attempting to prove complexity upper bounds for arithmetic theories. It took, for instance, 50 years to show that Büchi’s seminal approach for deciding Presburger arithmetic using finite-state automata runs in triply-exponential time and thus matches the upper bound of quantifier-elimination algorithms . However, understanding the algorithmic properties of automata-based decision procedures turned out to be surprisingly difficult and tedious, see e.g. . Automata-based decision procedures for arithmetic theories have also been of remarkable practical use and have been implemented in tools such as LASH or TaPAS .
Finite-state automata over finite and infinite words provide an elegant method for deciding linear arithmetic theories such as Presburger arithmetic or linear real arithmetic.
0 kommentar(er)
