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

Genetic and Evolutionary Computation Conference (GECCO)

作者： Dolson, Emily Michigan State Univ E Lansing MI 48824 USA

ISBN: (纸本)9798400701191

Lexicase selection is a state-of-the-art parent selection algorithm in evolutionary computation. Recently, there have been efforts to develop stronger theoretical analyses of lexicase selection. Many of these analysis hinge on calculating the probability of an individual solution being selected under lexicase selection. Discovering a fast way to perform this calculation would be very helpful to the development of theory regarding lexicase selection, and would also have implications for efforts to develop practical improvements to lexicase selection. Here, I prove that this problem of calculating selection probabilities under lexicase selection, which I name lex-prob, is NP-Hard. I achieve this proof by reducing SAT, a wellknown NP-Hard problem, to lex-prob in polynomial time. This reduction involves an intermediate step in which a popular variant of lexicase selection, is an element of-lexicase selection, is reduced to standard lexicase selection. This result also has deeper theoretical implications about the relationship between is an element of-lexicase selection and lexicase selection and the relationship between lex-prob and other NP-Hard problems. Finally, I present a highly-optimized brute-force algorithm (and open-source implementation) for performing these calculations. While the worst-case time complexity of this solution is, of course, exponential it is capable of solving realistically-sized instances of the problem in approximately 15 seconds.

关键词： lexicase selection computational complexity theory

来源：评论

学校读者我要写书评

暂无评论

P Systems with Evolutional Communication and Separation Rules 1

引用

9th Conference on Machines, Computations and Universality (MCU)

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

ISBN: (数字)9783031135026

ISBN: (纸本)9783031135026;9783031135019

In the framework of membrane computing, several interesting results concerning frontiers of efficiency between the complexity classes P and NP have been found by using different ingredients. One of the main characteristics of cell-like membrane systems is their rooted tree-like structure, where a natural parent-children membrane relationship exists, and objects can travel through the membranes. Separation rules are used as a method to obtain an exponential workspace in terms of membranes in polynomial time. Inspired by cell meiosis, objects from the original membrane are distributed between the two new membranes. In this work, P systems with evolutional symport/antiport rules and separation rules are used to give a solution to SAT, a well known NP-complete problem. One of the advantages of this solution is the use of the environment as a passive agent.

关键词： Membrane computing computational complexity theory P vs. NP problem Evolutional communication Symport/antiport

来源：评论

学校读者我要写书评

暂无评论

A theoretical formalism for analyzing agent-based models

引用

COMPLEX ADAPTIVE SYSTEMS MODELING 2014年第1期2卷 1页

作者： North, Michael J. Argonne Natl Lab Decis & Informat Sci Divr 9700 South Cass Ave Lemont IL 60439 USA Univ Chicago Chicago IL 60637 USA

Purpose: Following Holland, complex adaptive systems (CASs) are collections of interacting, autonomous, learning decision makers embedded in an interactive environment. Modeling CASs is challenging for a variety of reasons including the presence of heterogeneity, spatial relationships, nonlinearity, and, of course, adaptation. The challenges of modeling CASs can largely be overcome by using the individual-level focus of agent-based modeling. Agent-based modeling has been used successfully to model CASs in many disciplines. Many of these models were implemented using agent-based modeling software such as Swarm, Repast 3, Repast Simphony, Repast for High-Performance Computing, MASON, NetLogo, or StarLogo. All of these options use modular imperative architectures with factored agents, spaces, a scheduler, logs, and an interface. Many custom agent-based models also use this kind of architecture. This paper's contribution is to introduce and apply a theoretical formalism for analyzing modular imperative agent-based models of CASs. This paper includes an analysis of three example models to show how the formalism is useful for predicting the execution time and space requirements for representations of common CASs. Method: The paper details the formalism and then uses it to prove several new findings about modular imperative agent-based models. Results: It is proven that the asymptotic time and space performance ofmodular imperative agent-based modeling studies is computationally optimal for a common class of problems. Here 'optimal' means that no other technique can solve the same problem computationally using less asymptotic time or space. Modular imperative agent-based models are shown to be universal models, subject to the correctness of the Church-Turing thesis. Several other results are also proven about the time and space performance of modular imperative agent-based models. The formalism is then used to predict the performance of three models and the results are fou

关键词： Agent-based modeling computational complexity theory Random access stored-program machine

来源：评论

学校读者我要写书评

暂无评论

Logic and complexity in Distributed Computing

Logic and Complexity in Distributed Computing

引用

作者： Tuomo Lempiainen Aalto University

学位级别：博士

This dissertation studies the theory of distributed computing. In the distributed setting, computation is carried out by multiple independent computational units. They communicate with neighbouring units and collectively solve a problem. Systems of this kind are widespread in the information society as well as in the natural world: prime examples include the Internet, multi- processor computer systems, the cells of a biological organism and human social networks. Therefore it is important to gain knowledge on the fundamental capabilities and limitations of distributed systems. Our work takes place in the context of deterministic and synchronous message-passing models of distributed computing. Such models abstract away some possible features of distributed systems, such as asynchrony, congestion and faults, while putting emphasis on the amount of communication needed between the units. The computational units are expected to solve a problem related to the structure of the underlying communication network. More speciﬁcally, we study the standard LOCAL model, the standard port-numbering model and several weaker variants of the latter. The contributions of this dissertation are two-fold. First, we give new methods for studying distributed computing by establishing a strong connection between several weak variants of the port-numbering model and corresponding variants of modal logic. This makes it possible to apply existing logical tools, such as bisimulation, to understand computation in the distributed setting. We also give a full characterisation of the relationships between the models of computing, which has implications on the side of mathematical logic. Second, we prove the existence of various new non-empty complexity classes. One of our results studies the relationship between time and space complexity, which is a relatively new topic in distributed computing research. We demonstrate the existence of a problem that can be solved in a constant amount of space in a

关键词： distributed computing computational complexity theory port-numbering model LOCAL model graph problems LCL problems modal logic bisimulation

来源：评论

学校读者我要写书评

暂无评论

Circuits, Logic, and Games

Circuits, Logic, and Games

引用

Dagstuhl Seminar: Circuits, Logic, and Games 2010

作者： Rossman, Benjamin Schwentick, Thomas Thérien, Denis Vollmer, Heribert MIT Cambridge United States TU Dortmund Germany McGill U Montréal Canada Leibniz U Hannover Germany

来源：评论

学校读者我要写书评

暂无评论

computational complexity analysis for cognitive scientists 35

Computational complexity analysis for cognitive scientists

引用

35th Annual Meeting of the Cognitive Science Society - Cooperative Minds: Social Interaction and Group Dynamics, CogSci 2013

作者： van Rooij, Iris Kwisthout, Johan Blokpoel, Mark Wareham, Todd Radboud University Nijmegen Donders Institute for Brain Cognition and Behaviour Montessorilaan 3 Nijmegen6525 HR Netherlands Department of Computer Science Memorial University of Newfoundland St. John'sNL Canada

来源：评论

学校读者我要写书评

暂无评论

The weak call-by-value γ-calculus is reasonable for both time and space

The weak call-by-value γ-calculus is reasonable for both ti...

引用

Proceedings of the ACM on Programming Languages

作者： Forster, Yannick Kunze, Fabian Roth, Marc Saarland University Saarland Informatics Campus Saarbrücken Germany M2CI Saarbrücken Germany University of Oxford Oxford United Kingdom

We study the weak call-by-value γ-calculus as a model for computational complexity theory and establish the natural measures for time and space - the number of beta-reduction steps and the size of the largest term in a computation - as reasonable measures with respect to the invariance thesis of Slot and van Emde Boas from 1984. More precisely, we show that, using those measures, Turing machines and the weak call-by-value γ-calculus can simulate each other within a polynomial overhead in time and a constant factor overhead in space for all computations terminating in (encodings of) "true" or "false". The simulation yields that standard complexity classes like γ, NP, PSPACE, or EXP can be defined solely in terms of the γ-calculus, but does not cover sublinear time or space. Note that our measures still have the well-known size explosion property, where the space measure of a computation can be exponentially bigger than its time measure. However, our result implies that this exponential gap disappears once complexity classes are considered instead of concrete computations. We consider this result a first step towards a solution for the long-standing open problem of whether the natural measures for time and space of the γ-calculus are reasonable. Our proof for the weak call-by-value γ-calculus is the first proof of reasonability (including both time and space) for a functional language based on natural measures and enables the formal verification of complexity-theoretic proofs concerning complexity classes, both on paper and in proof assistants. The proof idea relies on a hybrid of two simulation strategies of reductions in the weak call-by-value γ-calculus by Turing machines, both of which are insufficient if taken alone. The first strategy is the most naive one in the sense that a reduction sequence is simulated precisely as given by the reduction rules; in particular, all substitutions are executed immediately. This simulation runs within a constant overhead in spac

关键词： Calculations computational complexity Differentiation (calculus) Formal verification Machinery Polynomials Turing machines Abstract machines computational complexity theory Functional languages Lambda calculus Reduction sequence Simulation strategies Time and space complexity Value reduction

来源：评论

学校读者我要写书评

暂无评论

A downward collapse within the polynomial hierarchy

引用

SIAM JOURNAL ON COMPUTING 1998年第2期28卷 383-393页

作者： Hemaspaandra, E Hemaspaandra, LA Hempel, H Univ Rochester Dept Comp Sci Rochester NY 14627 USA Univ Jena Inst Informat D-07743 Jena Germany Le Moyne Coll Dept Math Syracuse NY 13214 USA

Downward collapse (also known as upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the polynomial hierarchy. In particular, we prove that, for k >2, if P-Sigma kp[1] = P Sigma(kp[2]) then Sigma(k)(p) = Pi(k)(p) = PH. We extend this to obtain a more general downward collapse result.

关键词： computational complexity theory easy-hard arguments downward collapse polynomial hierarchy

来源：评论

学校读者我要写书评

暂无评论

Optimization on large interconnected graphs and networks using adiabatic quantum computation

引用

INTERNATIONAL JOURNAL OF QUANTUM INFORMATION 2023年第6期21卷 2350026-2350026页

作者： Padmasola, Venkat Chatterjee, Rupak Stevens Inst Technol Ctr Quantum Sci & Engn Dept Phys Hoboken NJ 07030 USA

In this paper, we demonstrate that it is possible to create an adiabatic quantum computing algorithm that solves the shortest path between any two vertices on an undirected graph with at most 3V qubits, where V is the number of vertices of the graph. We do so without relying on any classical algorithms, aside from creating an (V x V) adjacency matrix. The objective of this paper is to demonstrate the fact that it is possible to model large graphs on an adiabatic quantum computer using the maximum number of qubits available and random graph generators such as the Barabasi-Albert and the Erdos-Renyi methods which can scale based on a power law.

关键词： Quantum machine learning quantum optimization computational complexity theory graph algorithms scale free networks

来源：评论

学校读者我要写书评

暂无评论

Extending downward collapse from 1-ersus-2 queries to m-versus-m+1 queries

引用

SIAM JOURNAL ON COMPUTING 2005年第6期34卷 1352-1369页

作者： Hemaspaandra, E Hemaspaandra, LA Hempel, H Rochester Inst Technol Dept Comp Sci Rochester NY 14623 USA Univ Jena Inst Informat D-07743 Jena Germany Univ Wurzburg D-97070 Wurzburg Germany Univ Rochester Dept Comp Sci Rochester NY 14627 USA

The top part of Figure 1.1 shows some classes from the (truth-table) bounded- query and boolean hierarchies. It is well known that if either of these hierarchies collapses at a given level, then all higher levels of that hierarchy collapse to that same level. This is a standard "upward translation of equality" that has been known for over a decade. The issue of whether these hierarchies can translate equality downwards has proven vastly more challenging. In particular, with regard to Figure 1.1, consider the following claim: P-m-tt(Sigma kp) = P-m+1-tt(Sigma kp) double right arrow DIFFm(Sigma(p)(k)) = coDIFF(m)(Sigma(p)(k)) = BH(Sigma(p)(k)). (*) This claim, if true,says that equality translates downwards between levels of the bounded-query hierarchy and the boolean hierarchy levels that ( before the fact) are immediately below them. Until recently, it was not known whether (*) ever held, except for the degenerate cases m = 0 and k = 0. Then Hemaspaandra, Hemaspaandra, and Hempel [SIAM J. Comput., 28 ( 1999), pp. 383 - 393] proved that (*) holds for all m, for k > 2. Buhrman and Fortnow [ J. Comput. System Sci., 59 ( 1999), pp. 182 - 199] then showed that, when k = 2, (*) holds for the case m = 1. In this paper, we prove that for the case k = 2, (*) holds for all values of m. Since there is an oracle relative to which "for k = 1, (*) holds for all m" fails ( see Buhrman and Fortnow), our achievement of the k = 2 case cannot be strengthened to k = 1 by any relativizable proof technique. The new downward translation we obtain also tightens the collapse in the polynomial hierarchy implied by a collapse in the bounded- query hierarchy of the second level of the polynomial hierarchy.

关键词： computational complexity theory no-search easy-hard technique downward collapse upward separation downward translation of equality boolean hierarchy polynomial hierarchy

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：