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

P systems with proteins: a new frontier when membrane division disappears

JOURNAL OF MEMBRANE COMPUTING 2019年第1期1卷 29-39页

作者： Orellana-Martin, David Valencia-Cabrera, Luis Riscos-Nunez, Agustin Perez-Jimenez, Mario J. Univ Seville Dept Comp Sci & Artificial Intelligence Res Grp Nat Comp Avda Reina Mercedes S-N Seville 41012 Spain

P systems with active membranes are usually defined as devices hierarchically structured that evolve through rewriting rules. These rules take the inspiration on the chemical reactions that happen within a cell and the role of both the inner and the plasma membranes as a "filter", letting components pass or not. Classically, these systems are non-cooperative, that is, the left-hand side of the rules has at most one object. Using polarizations, dissolution or cooperation, these systems have been proved to have enough power to efficiently solve computationally hard problems, obtaining new complexity frontiers with respect to their non-cooperative counterparts. In this paper, division rules are interchanged by separation rules. While the first ones produce two new membranes and two new objects, duplicating the objects within the original one, separation rules distribute the objects of the original membrane into the two new created membranes, so no new objects are created in this way. To obtain new objects, a rule of the type [a -> a(2)] would be needed to accomplish that feature that seems to be necessary to obtain efficient solutions to NP-complete problems. Here, we present the limits when using separation rules instead of division rules.

关键词： Membrane Computing Active membranes Proteins computational complexity theory

来源：评论

学校读者我要写书评

暂无评论

A Non-canonical Example to Support P Is Not Equal to NP

引用

Transactions of Tianjin University 2011年第6期17卷 446-449页

作者：杨正瓴 School of Electrical Engineering and Automation Tianjin University Tianjin Key Laboratory of Process Measurement and Control

The more unambiguous statement of the P versus NP problem and the judgement of its hardness, are the key ways to find the full proof of the P versus NP problem. There are two sub-problems in the P versus NP problem. The first is the classifications of different mathematical problems (languages), and the second is the distinction between a non-deterministic Turing machine (NTM) and a deterministic Turing machine (DTM). The process of an NTM can be a power set of the corresponding DTM, which proves that the states of an NTM can be a power set of the corresponding DTM. If combining this viewpoint with Cantor's theorem, it is shown that an NTM is not equipotent to a DTM. This means that "generating the power set P(A) of a set A" is a non-canonical example to support that P is not equal to NP.

关键词： P versus NP computational complexity theory Cantor＇s theorem power set continuum hypothesis

来源：评论

学校读者我要写书评

暂无评论

Membrane creation and symport/antiport rules solving QSAT

引用

JOURNAL OF MEMBRANE COMPUTING 2022年第3期4卷 261-267页

作者： Orellana-Martin, David Valencia-Cabrera, Luis Perez-Jimenez, Mario J. Univ Seville Dept Comp Sci & Artificial Intelligence Res Grp Nat Comp Avda Reina Mercedes Seville 41012 Spain Univ Seville I3US SCORE Lab Avda Reina Mercedes Seville 41012 Spain

In Membrane Computing, different variants of devices can be found by changing both syntactical and semantic ingredients. These devices are usually called membrane systems or P systems, and they recall the structure and behavior of living cells in the nature. In this sense, rules are introduced as a way for objects to interact with membranes, giving P systems the ability to solve computational problems. Some of these rules, as division, separation and creation rules are inspired by the membrane division through the mitosis process or new membranes are created through gemmation. These rules seem to be crucial in the path to solve computationally hard problems. In this work, creation rules are used in classical P systems with symport/antiport rules, where objects travel through membranes without changing to achieve enough computational power to efficiently solve PSPACE-complete problems. More precisely, a solution to the QSAT problem is given by means of a uniform family of these systems. This paper was originally submitted to the International Conference on Membrane Computing 2021.

关键词： Membrane computing Membrane creation QSAT computational complexity theory

来源：评论

学校读者我要写书评

暂无评论

COUNTING CLASSES ARE AT LEAST AS HARD AS THE POLYNOMIAL-TIME HIERARCHY

引用

SIAM JOURNAL ON COMPUTING 1992年第2期21卷 316-328页

作者： TODA, S OGIWARA, M

In this paper, it is shown that many natural counting classes, such as PP, C = P, and MOD(k)P, are at least as computationally hard as PH (the polynomial-time hierarchy) in the following sense: for each K of the counting classes above, every set in K(PH) is polynomial-time randomized many-one reducible to a set in K with two-sided exponentially small error probability. As a consequence of the result, it is seen that all the counting classes above are computationally harder than PH unless PH collapses to a finite level. Some other consequences are also shown.

关键词： COUNTING complexity CLASSES POLYNOMIAL-TIME HIERARCHY RANDOMIZED REDUCIBILITY computational complexity theory

来源：评论

学校读者我要写书评

暂无评论

computational Resource Demands of a Predictive Bayesian Brain

引用

computational Brain and Behavior 2020年第2期3卷 174-188页

作者： Kwisthout, Johan van Rooij, Iris Donders Institute for Brain Cognition and Behaviour Radboud University Nijmegen Netherlands

There is a growing body of evidence that the human brain may be organized according to principles of predictive processing. An important conjecture in neuroscience is that a brain organized in this way can effectively and efficiently approximate Bayesian inferences. Given that many forms of cognition seem to be well characterized as a form of Bayesian inference, this conjecture has great import for cognitive science. It suggests that predictive processing may provide a neurally plausible account of how forms of cognition that are modeled as Bayesian inference may be physically implemented in the brain. Yet, as we show in this paper, the jury is still out on whether or not the conjecture is really true. Specifically, we demonstrate that each key subcomputation invoked in predictive processing potentially hides a computationally intractable problem. We discuss the implications of these sobering results for the predictive processing account and propose a way to move forward. © 2019, The Author(s).

关键词： Approximation Bayesian modeling computational complexity theory Intractability NP-hard Predictive processing Theoretical cognitive neuroscience

来源：评论

学校读者我要写书评

暂无评论

Descriptive complexity theories (logic and computer sciences)

引用

THEORIA-REVISTA DE TEORIA HISTORIA Y FUNDAMENTOS DE LA CIENCIA 2003年第1期18卷 47-58页

作者： Flum, J Univ Freiburg D-7800 Freiburg Germany

In this article we review some of the main results of descriptive complexity theory in order to make the reader familiarity with the nature of the investigations in this area. We start by presenting the characterization of automata recognizable languages by monadic second-order logic. Afterwards we explain the characterization of various logics by fixed-point logics. We assume familiarity with logic but try to keep knowledge of complexity theory to a minimum.

关键词： computational complexity theory complexity classes descriptive characterizations monadic second-order logic fixed-point logic Turing machine

来源：评论

学校读者我要写书评

暂无评论

NP problems, post-selection and weak measurements

NP problems, post-selection and weak measurements

引用

Conference on Quantum Information and Computation IV

作者： Tollaksen, Jeff Ghoshal, Debabrata George Mason Univ Coll Sci Fairfax VA 22030 USA

ISBN: (纸本)0819463000

If operations in a quantum computer were conditioned on the results of a subsequent post-selection measurement, then NP-complete problems could be solved in polynomial time. Using the natural connection between post-selection and NP, we show that this result is un-physical by considering constraints on new kinds of measurements which depend on the future post-selection in a non-trivial way. We review practical quantum information advantages of post-selection.

关键词： weak measurements weak values post-selection computational complexity theory probabilistic polynomial NP class of problems

来源：评论

学校读者我要写书评

暂无评论

On Algorithmic Statistics for Space-Bounded Algorithms 12th

On Algorithmic Statistics for Space-Bounded Algorithms

引用

12th International Computer Science Symposium in Russia (CSR)

作者： Milovanov, Alexey Natl Res Univ Higher Sch Econ Moscow Russia Moscow Inst Phys & Technol Dolgoprudnyi Russia Moscow MV Lomonosov State Univ Moscow Russia

ISBN: (纸本)9783319587479;9783319587462

Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice because Kolmogorov complexity is not computable. In this paper we develop algorithmic statistics using space-bounded Kolmogorov complexity. We prove an analogue of one of the main result of 'classic' algorithmic statistics (about the connection between optimality and randomness deficiences). The main tool of our proof is the Nisan-Wigderson generator.

关键词： Algorithmic statistics Kolmogorov complexity Nisan-Wigderson generator computational complexity theory Derandomization

来源：评论

学校读者我要写书评

暂无评论

Embedding and Canonizing Graphs of Bounded Genus in Logspace 14

Embedding and Canonizing Graphs of Bounded Genus in Logspace

引用

46th Annual ACM Symposium on theory of Computing (STOC)

作者： Elberfeld, Michael Kawarabayashi, Ken-ichi Rhein Westfal TH Aachen Aachen Germany Natl Inst Informat Tokyo Japan JST ERATO Kawarabayashi Large Graph Project Tokyo Japan

ISBN: (纸本)9781450327107

Graph embeddings of bounded Euler genus (that means, embeddings with bounded orientable or nonorientable genus) help to design time-efficient algorithms for many graph problems. Since linear-time algorithms are known to compute embeddings of any bounded Euler genus, one can always assume to work with embedded graphs and, thus, obtain fast algorithms for many problems on any class of graphs of bounded Euler genus. Problems on graphs of bounded Euler genus are also important from the perspective of finding space-efficient algorithms, mostly focusing on problems related to finding paths and matchings in graphs. So far, known space-bounded approaches needed the severe assumption that an embedding is given as part of the input since no space-efficient embedding procedure for nonplanar graphs was known. The present work sidesteps this assumption and shows that embeddings of any bounded Euler genus can be computed in deterministic logarithmic space (logspace);allowing to generalize results on the space complexity of path and matching problems from embedded graphs to graphs of bounded Euler genus. The techniques developed for the embedding procedure also allow to compute canonical representations and, thus, solve the isomorphism problem for graphs of bounded Euler genus in logspace.

关键词： computational complexity theory algorithmic graph theory logspace isomorphism graph embedding Euler genus

来源：评论

学校读者我要写书评

暂无评论

Playing Unique Games on Certified Small-Set Expanders 2021

Playing Unique Games on Certified Small-Set Expanders

引用

53rd Annual ACM SIGACT Symposium on theory of Computing (STOC)

作者： Bafna, Mitali Barak, Boaz Kothari, Pravesh K. Schramm, Tselil Steurer, David Harvard Univ Cambridge MA 02138 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Stanford Univ Stanford CA 94305 USA Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450380539

We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint graph via a hypercontractive inequality. Our algorithm is in fact more versatile, and succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is (informally speaking) "characterized" by a low-degree sum-of-squares proof. Our results are obtained by rounding low-entropy solutions - measured via a new global potential function - to sumof-squares (SoS) semidefinite programs. This technique adds to the (currently short) list of general tools for analyzing SoS relaxations for worst-case optimization problems. As corollaries, we obtain the first polynomial-time algorithms for solving any UG instance where the constraint graph is either the noisy hypercube, the short code or the Johnson graph. The prior best algorithm for such instances was the eigenvalue enumeration algorithm of Arora, Barak, and Steurer (2010) which requires quasi-polynomial time for the noisy hypercube and nearly-exponential time for the short code and Johnson graphs. All of our results achieve an approximation of 1 - epsilon vs delta for UG instances, where epsilon > 0 and delta > 0 depend on the expansion parameters of the graph but are independent of the alphabet size.

关键词： computational complexity theory approximation algorithms Sum of Squares algorithms Unique games conjecture

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：