检索结果-内蒙古大学图书馆

polynomial computability of certain rudimentary predicates

MATHEMATICAL NOTES 2003年第1-2期74卷 64-69页

作者： Marchenkov, SS Moscow MV Lomonosov State Univ Moscow 117234 Russia

The class of rudimentary predicates is defined as the smallest class of numerical predicates that contains the equality and concatenation predicates and is closed under the operations of propositional logic, explicit transformations, and bounded quantification. Two classes of rudimentary predicates are considered. The first of them consists of the predicates whose prenex normal form of a special type has the quantifier prefix of the form There ExistsFor All. Predicates of the second class can have an arbitrary quantifier prefix, but restrictions are imposed on the Skolem deciding functions. It is proved that any predicate from each of these classes can be computed by a suitable deterministic algorithm in polynomial time.

关键词： computational complexity polynomial computability prenex normal form rudimentary predicates propositional logic

来源：评论

学校读者我要写书评

暂无评论

FINITELY GENERATED STRUCTURES COMPUTABLE IN polynomial TIME

引用

SIBERIAN MATHEMATICAL JOURNAL 2022年第5期63卷 801-818页

作者： Alaev, P. E. Sobolev Inst Math Novosibirsk Russia

We give some simple description for the finitely generated structures with P-computable isomorphic presentation;i.e., presentation computable in polynomial time. The description is close to the formulation of a Remmel and Friedman theorem. We prove that each finitely generated substructure of a P-computable structure also has a P-computable presentation. The description is applied to the classes of finitely generated semigroups, groups, unital commutative rings and fields, as well as ordered unital commutative rings and fields. We prove that every finitely generated commutative ring or a field has a P-computable presentation.

关键词： computable structure polynomial computability algorithm complexity semigroup group ring field

来源：评论

学校读者我要写书评

暂无评论

Some Questions on polynomially Computable Representations for Generating Grammars and Backus–Naur Forms

引用

Siberian Advances in Mathematics 2022年第4期32卷 299-309页

作者： Nechesov, A.V. Sobolev Institute of Mathematics Novosibirsk 630090 Russian Federation

Abstract: In the present article, we consider the question on modeling Backus–Naur forms(BNF-systems) and generating grammars in GNF-systems. GNF-systems serve as the base forconstruction of monotone operators whose least fixed points are polynomially computable. Weobtain our results by construction of GNF-systems and application of a generalized polynomialanalog of Gandy’s fixed point theorem. This allows us to answer some questions on existence ofa polynomially computable representation for the set of derivations in generating ***, we show that, for each GNF-system modeling a BNF-system and every nonterminalsymbol in the BNF-system, the set of preimages in the GNF-system of representations of thissymbol is polynomially computable. This result allows us to encode all definable constructions ofthe BNF-system, including the syntax of programs in high-level programming languages, so thatthey become recognizable in polynomial time. © 2022, Pleiades Publishing, Ltd.

关键词： artificial intelligence Backus–Naur forms blockchain BNF-systems Chomsky grammars Gandy’s theorem generating grammars GNF-systems PAG-theorem polynomial computability programming languages semantic programming smart contracts

来源：评论

学校读者我要写书评

暂无评论

Inversion in P-Computable Fields 20th

Inversion in P-Computable Fields

引用

20th Conference on computability in Europe (CiE)

作者： Alaev, Pavel Novosibirsk State Univ Novosibirsk Russia Sobolev Inst Math SB RAS Novosibirsk Russia

ISBN: (纸本)9783031643088;9783031643095

We consider fields computable in polynomial time (P-computable). We prove that under some assumptions about a P-computable field (A,+, center dot) of characteristic 0, there exists a P-computable field (B,+, center dot) congruent to (A,+, center dot), in which x(-1) is not a primitive recursive function. In particular, this holds for the field Q of rational numbers.

关键词： computability polynomial computability computable structure field

来源：评论

学校读者我要写书评

暂无评论

Semantic Programming and polynomially Computable Representations

引用

Siberian Advances in Mathematics 2023年第1期33卷 66-85页

作者： Nechesov, A.V. Sobolev Institute of Mathematics Novosibirsk 630090 Russian Federation

Abstract: In the present article, we consider the question on existence of polynomially computablerepresentations for basic syntactic constructions of the first-order logic and for objects of semanticprogramming (such as L-programs andL-formulas). We prove that the sets of linear ortree-like derivations in the first-order predicate calculus admits a polynomially computablerepresentation. We also obtain a series of assertions that allow us to prove polynomialcomputability in a more efficient way. Among them, we mention the generalized PAG-theoremwith polynomially computable initial data and an assertion on p-iterative terms with weakened estimates. Ourresults may be useful for construction of logical programming languages, in smart contracts, aswell as for developing fast algorithms for automatic proof verification. © 2023, Pleiades Publishing, Ltd.

关键词： artificial intelligence Gandy theorem GNF-systems iterative terms PAG-theorem polynomial computability proof theory proof verification semantic programming smart contracts

来源：评论

学校读者我要写书评

暂无评论

Inversion operations in algebraic structures

引用

computability-THE JOURNAL OF THE ASSOCIATION CIE 2023年第4期12卷 315-322页

作者： Alaev, Pavel Sobolev Inst Math Pr Koptuga 4 Novosibirks 630090 Russia

We consider a wide series of classes of algorithmic complexity. We fix such a class and investigate the complexity of the inversion operation in classical algebraic structures, like groups or fields. In addition, we a... 详细信息

关键词： computability polynomial computability complexity of computations algebraic classes inversion operation

来源：评论

学校读者我要写书评

暂无评论

LIMITING polynomial APPROXIMATION OF COMPLEXITY CLASSES

引用

International Journal of Foundations of Computer Science 1990年第2期1卷 111-122页

作者： G. AUSIELLO M. PROTASI Dipartimento di Informatica e Sistemistica Università di Roma “La Sapienza” Via Eudossiana 18 00185 Rome Italy Dipartimento di Matematica Università di Roma “Tor Vergata” Via Orazio Raimondo 00173 Rome Italy

The concept of limiting approximation, formerly introduced by Gold for recursive functions, is applied to the polynomial level of complexity in order to determine meaningful characterizations of classes of functions and sets which are not (or which are not known to be) polynomially computable. In particular, characterizations of NP, PSPACE and other classes of elementary functions are provided in terms of limiting polynomial approximation. In addition trade-offs between the space required by the approximating functions and the rate of convergence of the approximation are shown.

关键词： Complexity classes Limiting approximation polynomial computability

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：