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

A SCHEMATIC DEFINITION OF QUANTUM polynomial time computability

JOURNAL OF SYMBOLIC LOGIC 2020年第4期85卷 1546-1587页

作者： Yamakami, Tomoyuki Univ Fukui Fac Engn 3-9-1 Bunkyo Fukui 9108507 Japan

In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper seeks the third model, which is a quantum analogue of the schematic (inductive or constructive) definition of (primitive) recursive functions. For quantum functions mapping finite-dimensional Hilbert spaces to themselves, we present such a schematic definition, composed of a small set of initial quantum functions and a few construction rules that dictate how to build a new quantum function from the existing ones. We prove that our schematic definition precisely characterizes all functions that can be computable with high success probabilities on well-formed quantum Turing machines in polynomial time, or equivalently uniform families of polynomial-size quantum circuits. Our new, schematic definition is quite simple and intuitive and, more importantly, it avoids the cumbersome introduction of the well-formedness condition imposed on a quantum Turing machine model as well as of the uniformity condition necessary for a quantum circuit model. Our new approach can further open a door to the descriptional complexity of quantum functions, to the theory of higher-type quantum functionals, to the development of new first-order theories for quantum computing, and to the designing of programming languages for real-life quantum computer

关键词： quantum computing quantum function quantum Turing machine quantum circuit schematic definition descriptional complexity polynomial-time computability normal form theorem

来源：评论

学校读者我要写书评

暂无评论

On the computational complexity of imperative programming languages

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-2期318卷 139-161页

作者： Kristiansen, L Niggl, KH Tech Univ Ilmenau Inst Theoret & Tech Informat D-98693 Ilmenau Germany Univ Oslo Fac Engn Oslo Norway

Two restricted imperative programming languages are considered: One is a slight modification of a loop language studied intensively in the literature, the other is a stack programming language over an arbitrary but fixed alphabet, supporting a suitable loop concept over stacks. The paper presents a purely syntactical method for analysing the impact of nesting loops on the running time. This gives rise to a uniform measure mu on both loop and stack programs, that is, a function that assigns to each such program P a natural number mu(P) computable from the syntax of P. It is shown that stack programs of mu-measure n compute exactly those functions computed by a Turing machine whose running time lies in Grzegorczyk class epsilon(ndivided by2). In particular, stack programs of mu-measure 0 compute precisely the polynomial-time computable functions. Furthermore, it is shown that loop programs of mu-measure n compute exactly the functions in epsilon(ndivided by2). In particular, loop programs of mu-measure 0 compute precisely the linear-space computable functions. (C) 2003 Elsevier B.V. All rights reserved.

关键词： implicit computational complexity imperative programming languages subrecursion theory Grzegorczyk hierarchy polynomial-time computability

来源：评论

学校读者我要写书评

暂无评论

Implicit characterizations of FPtime and NC revisited

引用

JOURNAL OF LOGIC AND ALGEBRAIC PROGRAMMING 2010年第1期79卷 47-60页

作者： Niggl, Karl-Heinz Wunderlich, Henning Tech Univ Ilmenau Fak Informat & Automatisierung Inst Theoret Informat D-98684 Ilmenau Germany Univ Ulm Fak Ingenieurwissensch & Informat Inst Theoret Informat D-89069 Ulm Germany

Various simplified or improved, and partly corrected well-known implicit characterizations of the complexity classes FPtime and NC are presented. Primarily, the interest is in simplifying the required simulations of various recursion schemes in the corresponding (implicit) framework, and in developing those simulations in a more uniform way, based on a step-by-step comparison technique, thus consolidating groundwork in implicit computational complexity. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Bounded and ramified forms of recursion Function algebra Implicit computational complexity NC polynomial-time computability

来源：评论

学校读者我要写书评

暂无评论

P=NPfor some structures over the binary words

引用

JOURNAL OF COMPLEXITY 2005年第4期21卷 557-578页

作者： Hemmerling, A Ernst Moritz Arndt Univ Greifswald Inst Math & Informat D-17487 Greifswald Germany

Over the universe of binary words, {0, 1}*, a type of structures of finite signature is defined that satisfy P = NP. This holds true both for the related classes of programs in which tests of equality (identity) of words are allowed, as well as for those in which no equality tests occur. The related structures correspond essentially to the pushdown data structures enriched by predicates which are suitably padded PSPACE-complete word sets. (c) 2005 Elsevier Inc. All rights reserved.

关键词： computability over structures computational complexity complexity classes polynomial-time computability p versus NP relativization

来源：评论

学校读者我要写书评

暂无评论

On an interpretation of safe recursion in light affine logic

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-2期318卷 197-223页

作者： Murawski, AS Ong, CHL Univ Oxford Comp Lab Oxford OX1 3QD England

We introduce a subalgebra BC- of Bellantoni and Cook's safe-recursion function algebra BC. Functions of the subalgebra have safe arguments that are non-contractible (i.e non-duplicable). We propose a definition of safe and normal variables in light affine logic (LAL), and show that BC- is the largest subalgebra that is interpretable in LAL, relative to that definition. Though BC- itself is not PF complete, there are extensions of it (by additional schemes for defining functions with safe arguments) that are, and are still interpretable in LAL and so preserve PF closure. We focus on one such which is BC- augmented by a definition-by-cases construct and a restricted form of definition-by-recursion scheme over safe arguments. As a corollary we obtain a new proof of the PF completeness of LAL. (C) 2003 Elsevier B.V. All rights reserved.

关键词： computational complexity light affine logic polynomial-time computability

来源：评论

学校读者我要写书评

暂无评论

The computational complexity of distance functions of two-dimensional domains

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期337卷 360-369页

作者： Chou, AW Ko, KI SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Clark Univ Dept Math & Comp Sci Worcester MA 01610 USA

We study the computational complexity of the distance function associated with a polynomial-time computable two-dimensional domains, in the context of the Turing machine-based complexity theory of real functions. It is proved that the distance function is not necessarily computable even if a two-dimensional domain is polynomial-time recognizable. On the other hand, if both the domain and its complement are strongly polynomial-time recognizable, then the distance function is polynomial-time computable if and only if P = NP. (c) 2004 Elsevier B.V. All rights reserved.

关键词： computational complexity polynomial-time computability two-dimensional domain distance function NP

来源：评论

学校读者我要写书评

暂无评论

P-comp versus P-samp questions on average polynomial domination

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2001年第10期E84D卷 1402-1410页

作者： Aida, S Tsukiji, T Nagoya Univ Grad Sch Human Informat Nagoya Aichi 4660826 Japan

In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable, distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP, P-samp) to (NP, P-comp). Th derive these and other related results, a prefix-search algorithm presented by Ben-David et al., will be modified to survive the average polynomial domination.

关键词： average-case complexity polynomial-time computability polynomial-time samplability domination

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：