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

The complexity of ferromagnetic ising with local fields

COMBINATORICS PROBABILITY & COMPUTING 2007年第1期16卷 43-61页

作者： Goldberg, Leslie Ann Jerrum, Mark Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Univ Edinburgh Div Informat JCMB Edinburgh EH9 3JZ Midlothian Scotland

We consider the complexity of approximating the partition function of the ferromagnetic Ising model with varying interaction energies and local external magnetic fields. Jerrum and Sinclair provided a fully polynomial randomized approximation scheme for the case in which the system is consistent in the sense that the local external fields all favour the same spin. We characterize the complexity of the general problem by showing that it is equivalent in complexity to the problem of approximately counting independent sets in bipartite graphs, thus it is complete in a logically defined subclass of #P previously studied by Dyer, Goldberg, Greenhill and Jerrum. By contrast, we show that the corresponding computational task for the q-state Potts model with local external magnetic fields and q > 2 is complete for all of #P with respect to approximation-preserving reductions.

关键词： computational-complexity MODEL

来源：评论

学校读者我要写书评

暂无评论

The complexity of concept languages

引用

INFORMATION AND COMPUTATION 1997年第1期134卷 1-58页

作者： Donini, FM Lenzerini, M Nardi, D Nutt, W UNIV ROMA LA SAPIENZA DIPARTIMENTO INFORMAT & SISTEMIST I-00198 ROME ITALY DFKI GMBH GERMAN RES CTR ARTIFICIAL INTELLIGENCE D-66123 SAARBRUCKEN GERMANY

A basic feature of Terminological Knowledge Representation Systems is to represent knowledge by means of taxonomies, here called terminologies, and to provide a specialized reasoning engine to do inferences on these structures, The taxonomy is built through a representation language called a concept language (or description logic), which is given a well-defined set-theoretic semantics. The efficiency of reasoning has often been advocated as a primary motivation for the use of such systems. The main contributions of the paper are: (1) a complexity analysis of concept satisfiability and subsumption for a wide class of concept languages;(2) algorithms for these inferences that comply with the worst-case complexity of the reasoning task they perform. (C) 1997 Academic Press.

关键词： Terminological representation systems Knowledge representation computational-complexity Empirical-analysis complexity Concept Language Knowledge Representation complexity classes Language Reasoning Inference engines

来源：评论

学校读者我要写书评

暂无评论

Reducing the Multiplier-complexity of Massively Parallel Polyphase 2D IIR Broadband Beam Filters

引用

CIRCUITS SYSTEMS AND SIGNAL PROCESSING 2012年第3期31卷 1229-1243页

作者： Madanayake, Arjuna Gunaratne, Thushara K. Bruton, Leonard T. Univ Akron Akron OH 44325 USA Univ Calgary Calgary AB T2N 1N4 Canada

The superior broadband performance of 2D IIR frequency-planar beam filters, relative to conventional 2D FIR true-time-delay beamforming, has recently been reported using computational electromagnetics and real-time emulations on an antenna test range, resulting in significant improvements of bit-error-rates (BERs) in the presence of broadband interference. Further, massively parallel systolic VLSI circuit polyphase architectures have also been reported (Madanayake et al. in Int. J. Circuit Theory Appl. 2010) for the case of the direct-form signal flow graph (SFG) architecture, operating at a maximum throughput of M-(antenna)-frames-per-clock-cycle (MFPCC). The superior broadband performance of 2D IIR frequency-planar beam filters is extended here from the direct-form signal flow graph (SFG) architecture (Madanayake et al. in Int. J. Circuit Theory Appl. 2010) to the novel differential-form SFG architecture in order to reduce overall complexity. The proposed method employs a differential-form polyphase 2D IIR frequency-planar beam SFG, and a corresponding circuit architecture, to implement the required input-output 2D space-time difference equation. The resultant digital hardware has the significant advantage of much-reduced multiplier complexity, relative to the direct-form structure. For example, when look-ahead pipelining is not employed and for polyphase architectures having two, three, and four phases, the corresponding reductions in multiplier complexity are 20%, 28.6% and 33.3%, respectively. A proof-of-concept prototype circuit is designed and implemented on a Xilinx Sx35 FPGA device for the two-phase case, operating at a frame-rate of 132 million linear frames per second on the uniform linear array (ULA), corresponding to 2-frames-per-clock-cycle at a circuit clock frequency of 66 MHz. The circuit is optimized for low critical path delays (CPDs) using look-ahead pipelining of order three. For ultra-wideband (UWB) radio-frequency (RF) implementations, in such

关键词： 2-dimensional (2D) computational-complexity Broadband Beam filters FPGA Hardware IIR digital filter Massively parallel Multirate Polyphase Time-interleaved VLSI

来源：评论

学校读者我要写书评

暂无评论

Tractable fragments of Presburger Arithmetic

引用

THEORY OF COMPUTING SYSTEMS 2005年第5期38卷 647-668页

作者： Subramani, K W Virginia Univ LDCSEE Morgantown WV 26506 USA

In this paper we introduce a problem called Quantified Integer Programming, which generalizes the Quantified Satisfiability problem (QSAT). In a Quantified Integer Program (QIP) the program variables can assume arbitrary integral values, as opposed to the boolean values that are assumed by the variables of an instance of QSAT. QIPs naturally represent two-person integer matrix games. The Quantified Integer Programming problem is PSPACE-hard in general, since the QSAT problem is PSPACE-complete. Quantified Integer Programming can be thought of as a restriction of Presburger Arithmetic, in that we allow only conjunctions of linear inequalities. We focus on analyzing various special cases of the general problem, with a view to discovering subclasses that are tractable. Subclasses of the general QIP problem are obtained by restricting either the constraint matrix or quantifier specification or both. We show that if the constraint matrix is totally unimodular, the problem of deciding a QIP can be solved in polynomial time. We also establish the computational complexities of Oblivious strategy games and Clairvoyant strategy games.

关键词： computational-complexity CONSTRAINT DATABASES DATALOG QUERIES FASTALGORITHMS TIME ALGORITHM 2 VARIABLES PROGRAMS FLOW

来源：评论

学校读者我要写书评

暂无评论

Reflective relational machines

引用

INFORMATION AND COMPUTATION 1998年第2期143卷 110-136页

作者： Abiteboul, S Papadimitriou, CH Vianu, V Inst Natl Rech Informat & Automat F-78153 Le Chesnay France Univ Calif Berkeley Dept EECS Berkeley CA 94720 USA Univ Calif San Diego CSE 0114 La Jolla CA 92093 USA

We propose a model of database programming with reflection (dynamic generation of queries within the host programming language), called the reflective relational machine, and characterize the power of this machine in terms of known complexity classes. In particular, the polynomial-time restriction of the reflective relational machine is shown to express PSPACE, and to correspond precisely to uniform circuits of polynomial depth and exponential size. This provides an alternative, logic-based formulation of the uniform circuit model, which may be more convenient for problems naturally formulated in logic terms, and establishes that reflection allows for more "intense" parallelism, which is not attainable otherwise (unless P = PSPACE). We also explore the power of the reflective relational machine subject to restrictions on the number of variables used, emphasizing the case of sublinear bounds. (C) 1998 Academic Press.

关键词： computational-complexity Logic Expressibility Queries

来源：评论

学校读者我要写书评

暂无评论

complexity and compilability of diagnosis and recovery of graph-based systems

引用

INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS 2005年第10期20卷 1053-1076页

作者： Liberatore, P Univ Roma La Sapienza Dipartimento Informat & Sistemist Rome Italy

This article reports complexity results on diagnosis of systems modeled as graphs. In this model introduced by Rao and Viswanadham, each component is a node of a graph, and an edge indicates that faults propagate from one component to the other one. The basic problem of diagnosis is known to be polynomial and NP-complete in the cases of single faults and multiple faults, respectively. We extend the complexity analysis to the case of faulty alarms, and also consider the problem of limiting the propagation of faults. We show that none of the considered diagnosis problems can be simplified by preprocessing the graph. (c) 2005 Wiley Periodicals, Inc.

关键词： computational-complexity INTRACTABLE PROBLEMS OPERATIVE DIAGNOSIS FAULT-PROPAGATION

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic algorithms for maintaining shortest paths trees

引用

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC 2000年第2期34卷 251-281页

作者： Frigioni, D Marchetti-Spaccamela, A Nanni, U Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy Univ Rome Dipartimento Informat & Sistemist I-00198 Rome Italy Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal query time. The cost of the update operations depends on the class of the considered graph and on the number of the output updates, i.e., on the number of vertices that, due to an edge modification, either change the distance from the source or change the parent in the shortest paths tree. We first show that, if we deal only with updates on the weights of edges, then the update procedures require O(log n) worst case time per output update for several classes of graphs, as in the case of graphs with bounded genus, bounded arboricity, bounded degree, bounded treewidth, and bounded pagenumber. For general graphs with n vertices and m edges the algorithms require O(root m log n) worst case time per output update. We also show that, if insertions and deletions of edges are allowed, then similar amortized bounds hold. (C) 2000 Academic Press.

关键词： computational-complexity Planar graphs Combinatorial Digraphs complexity classes Paths Byways Bounded deletions search time Edges Dynamic algorithms directed graphs Output planning drawings

来源：评论

学校读者我要写书评

暂无评论

Recognition algorithms in knot theory

引用

RUSSIAN MATHEMATICAL SURVEYS 2003年第6期58卷 1093-1139页

作者： Dynnikov, IA Moscow MV Lomonosov State Univ Lab Int Franco Russe Math & Interact Informat & P Moscow Russia

In this paper the problem of constructing algorithms for comparing knots and links is discussed. A survey of existing approaches and basic results in this area is given. In particular, diverse combinatorial methods for representing links are discussed, the Haken algorithm for recognizing a trivial knot (the unknot) and a scheme for constructing a general algorithm (using Haken's ideas) for comparing links are presented, an approach based on representing links by closed braids is described, the known algorithms for solving the word problem and the conjugacy problem for braid groups are described, and the complexity of the algorithms under consideration is discussed. A new method of combinatorial description of knots is given together with a new algorithm (based on this description) for recognizing the unknot by using a procedure for monotone simplification. In the conclusion of the paper several problems are formulated whose solution could help to advance towards the 'algorithmization' of knot theory.

关键词： STUDYING LINKS CLOSED BRAIDS computational-complexity 3-MANIFOLDS EQUATIONS GEOMETRY

来源：评论

学校读者我要写书评

暂无评论

Measurable notions of complexity and their relationship to biological complexity

引用

CHEMISTRY & BIODIVERSITY 2007年第11期4卷 2656-2669页

作者： Brooks, J. Paul Virginia Commonwealth Univ Operat Res & Ctr Study Biol Compplexity Dept Stat Sci Richmond VA 23284 USA

complexity is often invoked as a motivation for a systems approach to biology. We review three measurable notions of complexity from the areas of computation and data analysis. These measures have each led to mathematical theory and to further insight on the complexity of objects, demonstrating the benefits of having a well-defined measure of complexity. Each measure is applicable in the study of particular biological systems;however, none is satisfactory to serve as a universal measure of biological complexity. The study of biological systems will likely require numerous measures of complexity, each appropriate for analysis in specific settings.

关键词： MINIMUM DESCRIPTION LENGTH computational-complexity PRINCIPLE TREES

来源：评论

学校读者我要写书评

暂无评论

Adaptation in stochastic tunneling global optimization of complex potential energy landscapes

引用

EUROPHYSICS LETTERS 2006年第6期74卷 944-950页

作者： Hamacher, K. Univ Calif San Diego Ctr Theoret Biol Phys La Jolla CA 92093 USA

Global optimization remains one of the great challenges in scientific computing. One particular successful approach is the usage of tunneling functions to cross barriers and transition states more easily thus allowing for a fast scan of the potential energy surface under investigation. In this paper we develop for the first time a performance measurement procedure for stochastic tunneling approaches and derive an adaptive algorithm that is steered by this performance measure. The proposed algorithm is based on a scale-free measure and thus applicable to general stochastic optimization schemes. We found for a very hard optimization problem the computational effort to be some order of magnitude lower while at the same time increasing the accuracy by a factor of three.

关键词： MONTE-CARLO ATOMIC CLUSTERS computational-complexity TEMPERING METHOD MINIMIZATION ALGORITHM PROTEIN MINIMUM CHEMISTRY DOCKING

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：