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

3rd italian conference on algorithms and complexity, ciac 1997

3rd italian conference on algorithms and complexity, ciac 1997

ISBN: (纸本)3540625925

The proceedings contain 27 papers. The special focus in this conference is on algorithms and complexity. The topics include: algorithms and data structures for control dependence and related compiler problems;embedding interconnection networks in grids via the layered cross product;finding optimum k-vertex connected spanning subgraphs;the optimum cost chromatic partition problem;fault tolerant k-center problems;syntactic characterization in LISP of the polynomial complexity classes and hierarchy;on the drift of short schedules;on removing non-degeneracy assumptions in computational geometry;maintaining maxima under boundary updates;an optimal algorithm for one-separation of a set of isothetic polygons;nice drawings for planar bipartite graphs;area requirement of gabriel drawings;design of reliable combinatorial algorithms using certificates;an improved deterministic algorithm for generalized random sampling;polynomial time algorithms for some self-duality problems;a note on updating suffix tree labels;relaxed balanced red-black trees;the algorithmic complexity of chemical threshold testing;a meticulous analysis of mergesort programs;BSP-like external-memory computation;topological chaos for elementary cellular automata;on the complexity of balanced boolean functions;on sets with easy certificates and the existence of one-way permutations;isomorphism for graphs of bounded distance width;hardness of approximating problems on cubic graphs and tree contractions and evolutionary trees.

关键词：

来源：评论

学校读者我要写书评

暂无评论

On the complexity of balanced Boolean functions 3rd

引用

3rd italian conference on algorithms and complexity (ciac 97)

作者： Bernasconi, A Univ Pisa Dipartimento Informat Pisa Italy CNR Ist Matemat Computaz I-56100 Pisa Italy

This paper introduces the notions of balanced and strongly balanced Boolean functions and examines the complexity of these functions using harmonic analysis on the hypercube. The results are applied to derive a lower ... 详细信息

ISBN: (纸本)3540625925

关键词： Boolean functions

来源：评论

学校读者我要写书评

暂无评论

Algorithmic complexity of chemical threshold testing

Algorithmic complexity of chemical threshold testing

引用

Proceedings of the 1997 3rd italian conference on algorithms and complexity, ciac'97

作者： Damaschke, P.

来源：评论

学校读者我要写书评

暂无评论

Characterizing the existence of one-way permutations

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期244卷 257-261页

作者： Hemaspaandra, LA Rothe, J Univ Rochester Dept Comp Sci Rochester NY 14627 USA Univ Jena Inst Informat D-07740 Jena Germany

We establish a condition necessary and sufficient for the existence of one-way permutations: One-way permutations exist if and only if there exist total one-one one-way functions whose range is P-rankable. (C) 2000 El... 详细信息

关键词： one-way permutations one-way functions ranking worst-case cryptography computational complexity

来源：评论

学校读者我要写书评

暂无评论

Syntactic characterization in Lisp of the polynomial complexity classes and hierarchy 3rd

引用

3rd italian conference on algorithms and complexity (ciac 97)

作者： Caporaso, S Zito, M Galesi, N Covino, E Univ Bari Dipartimento Informat I-70126 Bari Italy Univ Warwick Coventry CV4 7AL W Midlands England Univ Politecn Catalunya Barcelona Spain Univ Ulm Abt Informat D-89069 Ulm Germany

ISBN: (纸本)3540625925

The definition of a class C of functions is syntactic if membership to C can be decided from the construction of its elements. Syntactic characterizations of PTIMEF, of PSPACEF, of the polynomial hierarchy PH, and of its subclasses Delta(n)(p) are presented. They are obtained by progressive restrictions of recursion in Lisp, and may be regarded as predicative according to a foundational point raised by Leivant.

关键词： Syntactics

来源：评论

学校读者我要写书评

暂无评论

The algorithmic complexity of chemical threshold testing 3rd

引用

3rd italian conference on algorithms and complexity (ciac 97)

作者： Damaschke, P Fernuniversitat Hagen D-58084 Hagen Germany

ISBN: (纸本)3540625925

Let us be given a set of water samples where possibly some are contaminated with a chemical substance. We wish to find these "defective" samples and their concentrations. Assume that there is an indicator available that can only detect whether the concentration is at least a known threshold, but we may split, merge, and dilute different samples. This problem is a generalized version of the well-known group testing problem and is also related to learning Boolean threshold functions. First we consider the problem of approximating the concentration in a single sample by a threshold indicator only. We present a practical and efficient strategy that achieves a close approximation using a small number of tests and auxiliary operations. This strategy is formulated as a pebble moving game on a suitable graph. Then we give principal asymptotic complexity results for finding, in a set of samples, those samples where the concentration exceeds a given limit. The results for the number of tests are asymptotically optimal, furthermore we propose a way for the efficient use of the other resources.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Finding optimum k-vertex connected spanning subgraphs: Improved approximation algorithms for k = 3, 4, 5 3rd

引用

3rd italian conference on algorithms and complexity (ciac 97)

作者： Dinitz, Y Nutov, Z Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Technion Israel Inst Technol Dept Math IL-32000 Haifa Israel

ISBN: (纸本)3540625925

The problem of finding a minimum weight t-vertex connected spanning subgraph is considered. For k > 1, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there are k internally vertex-disjoint paths to every other vertex), we derive polynomial time approximation algorithms for several values of k. (i) For k = 3, we give an algorithm with approximation factor 2. This improves the best previously known factor 3. (ii) For k = 4 and k = 5, we give an algorithm with approximation factor 3. This improves the best previously known factors 4 1/6 and 4 17/30 respectively.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

RSN1-tt (NP) distinguishes robust many-one and Turing completeness 3rd

引用

3rd italian conference on algorithms and complexity, ciac 1997

作者： Hemaspaandra, Edith Hemaspaandra, Lane A. Hempel, Harald Department of Mathematics Le Moyne College SyracuseNY13214 United States Department of Computer Science University of Rochester RochesterNY14627 United States Inst. für Informatik Friedrich-Schiller-Universität Jena Jena07743 Germany

ISBN: (纸本)3540625925

Do complexity classes have many-one complete sets if and only if they have Turing-complete sets? We prove that there is a relativized world in which a relatively natural complexity class—namely a downward closure of NP, RSN1-tt (NP)—has Turing-complete sets but has no many-one complete sets. In fact, we show that in the same relativized world this class has 2-truth-table complete sets but lacks 1-truth-table complete sets. As part of the groundwork for our result, we prove that RSN1-tt (NP) has many equivalent forms having to do with ordered and parallel access to NP and NP ∩ coNP. © Springer-Verlag Berlin Heidelberg 1997.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

algorithms and complexity 1

引用

丛书名： Lecture Notes in Computer Science

1000年

ISBN: (数字)9783540683230

ISBN: (纸本)9783540625926

This book constitutes the refereed proceedings of the Third italian conference on algorithms and complexity, ciac'97, held in Rome, Italy in March 1997.;The 25 revised full papers included in the volume were carefully selected from a total of 74 submissions; also included is an invited paper and an invited abstract. All in all, the papers present an interesting snapshot of current research activities and recent results in theory and applications of sequential, distributed, and parallel algorithms, data structures, and computational complexity.

关键词： Theory of Computation Mathematical Logic and Foundations Applications of Mathematics Algorithm Analysis and Problem complexity Computation by Abstract Devices Data Structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：