Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.     

Consequences of neocompact quantifier elimination

We provide some consequences of a Quantifier Elimination Property and related properties previously introduced (see [4]) in the setting of Banach space structures. We further consider some applications of quantifierfree definability, such as strict convexity via the definability of certain mapping and the continuity of definable functions.     

Dines—Fourier—Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields

A constructive procedure using Dines—Fourier—Motzkin elimination is given for eliminating quantifiers in a linear first order formula over ordered fields. An ensuing transfer principle is illustrated by showing that a locally one-to-one affine map is globally one-to-one and onto all over ordered fields.This research is based on work supported in part by the National Science Foundation under Grant DMS-86-03232, by the Department of Energy grant DE-FG03-87ER25028 and by the United States-Israel Binational Science Foundation Grant 85-00295.     

Horn函数可满足性的复杂性(英文)

本文证明了 Ｈｏｒｎ函数的极大可满足性即使是限制在如下两种情况中的任何一种也是 ＭＡＸ ＳＮＰ困难的,第一种情况是每个公式都是二次的,第二种是公式中每一个非单位子句有且只有一个补元,这意味着在这档两种情况下没有多项式的近似算法,除非Ｐ＝ＮＰ．     

On the Boolean connectivity problem for Horn relations

Gopalan et al. studied in [P. Gopalan, P.G. Kolaitis, E.N. Maneva, C.H. Papadimitriou, The connectivity of Boolean satisfiability: computational and structural dichotomies, in: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, 2006, pp. 346-357] and [P. Gopalan, P.G. Kolaitis, E.N. Maneva, C.H. Papadimitriou, The connectivity of Boolean satisfiability: computational and structural dichotomies, SIAM J. Comput. 38 (6) (2009) 2330-2355] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on the connectivity problems in Schaefer’s framework. A set S of logical relations is Schaefer if all relations in S are either bijunctive, Horn, dual Horn, or affine. They first conjectured that the connectivity problem for Schaefer is in P. We disprove their conjecture by showing that there exists a set S of Horn relations such that the connectivity problem for S is -complete. We also investigate a tractable aspect of Horn and dual Horn relations with respect to characteristic sets.     

Quantifier elimination for the theory of algebraically closed valued fields with analytic structure

The theory of algebraically closed non‐Archimedean valued fields is proved to eliminate quantifiers in an analytic language similar to the one used by Cluckers, Lipshitz, and Robinson. The proof makes use of a uniform parameterized normalization theorem which is also proved in this paper. This theorem also has other consequences in the geometry of definable sets. The method of proving quantifier elimination in this paper for an analytic language does not require the algebraic quantifier elimination theorem of Weispfenning, unlike the customary method of proof used in similar earlier analytic quantifier elimination theorems. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Preservation theorems for bounded formulas

In this paper we naturally define when a theory has bounded quantifier elimination, or is bounded model complete. We give several equivalent conditions for a theory to have each of these properties. These results provide simple proofs for some known results in the model theory of the bounded arithmetic theories like CPV and PV₁. We use the mentioned results to obtain some independence results in the context of intuitionistic bounded arithmetic. We show that, if the intuitionistic theory of polynomial induction on strict formulas proves decidability of formulas, then P=NP. We also prove that, if the mentioned intuitionistic theory proves , then P=NP.     

Satisfiability of mixed Horn formulas

In this paper the class of mixed Horn formulas is introduced that contain a Horn part and a 2-CNF (conjunctive normal form) (also called quadratic) part. We show that SAT remains NP-complete for such instances and also that any CNF formula can be encoded in terms of a mixed Horn formula in polynomial time. Further, we provide an exact deterministic algorithm showing that SAT for mixed Horn formulas containing n variables is solvable in time O(2^0.5284n). A strong argument showing that it is hard to improve a time bound of O(2^n/2) for mixed Horn formulas is provided. We also obtain a fixed-parameter tractability classification for SAT restricted to mixed Horn formulas C of at most k variables in its positive 2-CNF part providing the bound O(∥C∥2^0.5284k). We further show that the NP-hard optimization problem minimum weight SAT for mixed Horn formulas can be solved in time O(2^0.5284n) if non-negative weights are assigned to the variables. Motivating examples for mixed Horn formulas are level graph formulas [B. Randerath, E. Speckenmeyer, E. Boros, P. Hammer, A. Kogan, K. Makino, B. Simeone, O. Cepek, A satisfiability formulation of problems on level graphs, ENDM 9 (2001)] and graph colorability formulas.     

Linear CNF formulas and satisfiability

In this paper, we study linear CNF formulas generalizing linear hypergraphs under combinatorial and complexity theoretical aspects w.r.t. SAT. We establish NP-completeness of SAT for the unrestricted linear formula class, and we show the equivalence of NP-completeness of restricted uniform linear formula classes w.r.t. SAT and the existence of unsatisfiable uniform linear witness formulas. On that basis we prove NP-completeness of SAT for uniform linear classes in a resolution-based manner by constructing large-sized formulas. Interested in small witness formulas, we exhibit some combinatorial features of linear hypergraphs closely related to latin squares and finite projective planes helping to construct rather dense, and significantly smaller unsatisfiable k-uniform linear formulas, at least for the cases k=3,4.     

素数阶群理论的量词消去算法及其上界

在以前的一些工作中,作者已经证明语言(?)={+,0,e)上素数阶群的理论T有量词消去性质并研究了它的判定问题的复杂性.本文在此基础上将利用T的判定问题的复杂性结果给出理论T的量词消去的一个算法,同时给出该算法的复杂性上界.     

Quantifier elimination for elementary geometry and elementary affine geometry

We introduce new first‐order languages for the elementary n‐dimensional geometry and elementary n‐dimensional affine geometry (n ≥ 2), based on extending $\mathsf {FO}(\beta ,\equiv )$ and $\mathsf {FO}(\beta )$, respectively, with new function symbols. Here, β stands for the betweenness relation and ≡ for the congruence relation. We show that the associated theories admit effective quantifier elimination.     

一类变价格的物资库存优化模型

本文提出一类变价格的物资库存优化模型，对模型作了近似处理并求解，从而确定最佳订购次数．     

Some inequalities and asymptotic formulas for eigenvalues on Riemannian manifolds

In this paper, we establish sharp inequalities for four kinds of classical eigenvalues in bounded domains of Riemannian manifolds. We also obtain the Weyl-type asymptotic formulas for the eigenvalues of the buckling and clamped plate problems in bounded domains of Riemannian manifolds. In addition, we give a negative answer to the Payne conjecture for the one-dimensional case.     

Area and coarea formulas for the mappings of Sobolev classes with values in a metric space

We prove the metric differentiability and approximate metric differentiability for some broad classes of mappings with values in a metric space, including Sobolev classes. By way of application, we derive some metric analogs of area and coarea formulas.     

Mehler's formulas for the univariate complex Hermite polynomials and applications

We give 2 widest Mehler's formulas for the univariate complex Hermite polynomials , by performing double summations involving the products and . They can be seen as the complex analogues of the classical Mehler's formula for the real Hermite polynomials. The proof of the first one is based on a generating function giving rise to the reproducing kernel of the generalized Bargmann space of level m. The second Mehler's formula generalizes the one appearing as a particular case of the so‐called Kibble‐Slepian formula. The proofs we present here are direct and more simpler. Moreover, direct applications are given and remarkable identities are derived.