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

14th International Conference on Developments in Language Theory

作者： Jeandel, Emmanuel Vanier, Pascal Aix Marseille Univ CNRS LIF F-13013 Marseille France

Things and tiling systems are an abstract concept that arise both as a computational model and as a dynamical system. In this paper, we prove an analog of the theorems of Fagin [9] and Selman and Jones [14] by charact... 详细信息

ISBN: (纸本)9783642144547

关键词： computational and structural complexity tilings dynamical systems

来源：评论

学校读者我要写书评

暂无评论

Approximation Algorithms for 3D Orthogonal Knapsack

引用

Journal of Computer Science & Technology 2008年第5期23卷 749-762页

作者： Florian Diedrich Rolf Harren Klaus Jansen Ralf Thle Henning Thomas Institute of Computer Science University of Kiel Max-Planck-Institut für Informatik Campus E1466123 Saarbrücken Germany Department of Computer Science ETH ZurichZurich Switzerland

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 ＋ ε and 8 ＋ ε, as well as an algorithm with approximation ratio 7 ＋ ε that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 ＋ ε and 5 ＋ ε, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.

关键词： approximation algorithm computational and structural complexity geometric configurations

来源：评论

学校读者我要写书评

暂无评论

Splitting NP-complete sets

引用

SIAM JOURNAL ON COMPUTING 2008年第5期37卷 1517-1535页

作者： Glasser, Christian Pavan, A. Selman, Alan L. Zhang, Liyu Univ Wurzburg Lehrstuhl Informat 4 D-97074 Wurzburg Germany Iowa State Univ Dept Comp Sci Ames IA 50010 USA SUNY Buffalo Dept Comp Sci Buffalo NY 14260 USA Univ Texas Brownsville Dept Comp Sci & Informat Syst Brownsville TX 78520 USA

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long-standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glaber et al., complete sets for all of the following complexity classes are m-mitotic: NP, coNP, circle plus P, PSPACE, and NEXP, as well as all levels of PH, MODPH, and the Boolean hierarchy over NP. In the cases of NP, PSPACE, NEXP, and PH, this at once answers several well-studied open questions. These results tell us that complete sets share a redundancy that was not known before. In particular, every NP-complete set A splits into two NP-complete sets A(1) and A(2). We disprove the equivalence between autoreducibility and mitoticity for all polynomial-time-bounded reducibilities between 3-tt-reducibility and Turing-reducibility: There exists a sparse set in EXP that is polynomial-time 3-tt-autoreducible, but not weakly polynomial-time T-mitotic. In particular, polynomial-time T-autoreducibility does not imply polynomial-time weak T-mitoticity, which solves an open question by Buhrman and Torenvliet.

关键词： computational and structural complexity NP-complete sets autoreducibility mitoticity

来源：评论

学校读者我要写书评

暂无评论

Path-Constrained Relaxed Schedulability Analysis

Path-Constrained Relaxed Schedulability Analysis

引用

9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

作者： Andrei, Stefan Chakraborty, Samarjit Lamar Univ Dept Comp Sci Beaumont TX 77710 USA Natl Univ Singapore Sch Comp Singapore Singapore 117548 Singapore

ISBN: (纸本)9780769530789

The schedulability analysis problem for many realistic task models is known to be hard (NP or coNP). As this severely restricts the application of these task models, recently there has been a considerable amount of interest in relaxed or approximate notions of schedulability, with the hope that they can be checked more efficiently. In this paper we introduce yet another natural notion Of relaxed schedulability, which is parameterized in terms of the number of paths in a task set. In the model we consider, each task is represented by a directed acyclic graph where the nodes of such a graph are annotated with execution times and deadlines. Our proposed notion of schedulability allows a certain number of paths from each task graph to be non-schedulable. For describing the relaxed schedulability analysis, we formally define a measure called pseudo-K-schedulability, which corresponds to the situation when the task set has exactly K schedulable paths. At one extreme is the classical notion of schedulability analysis, where the problem is NP hard in our and many other task models. At the other extreme of this spectrum we have the trivial notion of schedulability analysis, where no path needs to be schedulable. Problems in between allow for a flexible notion of schedulability. This paper studies the relaxed schedulability because not all paths in a code are executed. This paper shows a fundamental result, namely the membership of the pseudoschedulability problem to the class of #P-hard problems.

关键词： computational and structural complexity scheduling feasibility analysis SAT problem

来源：评论

学校读者我要写书评

暂无评论

Extended skew partition problem

引用

DISCRETE MATHEMATICS 2006年第19-20期306卷 2438-2449页

作者： Dantas, Simone de Figueiredo, Celina M. H. Gravier, Sylvain Klein, Sulamita Univ Fed Rio de Janeiro COPPE BR-21941 Rio De Janeiro Brazil Univ Fed Rio de Janeiro Inst Matemat BR-21941 Rio De Janeiro Brazil CNRS Lab Leibniz F-75700 Paris France

A skew partition as defined by Chvatal is a partition of the vertex set of a graph into four nonempty parts A(1), A(2), B-1, B-2 such that there are all possible edges between A(1) and A(2), and no edges between B-1 and B-2. We introduce the concept of (n(1), n(2))-extended skew partition which includes all partitioning problems into n(1) + n(2) nonempty parts A(1),..., An(1), B-1,...,Bn-2, such that there are all possible edges between the A(i) parts, no edges between the B-j parts, i is an element of (1, ..., n(1)}, j is an element of {1,..., n(2)}, which generalizes the skew partition. We present a polynomial-time algorithm for testing whether a graph admits an (n(1), n(2))-extended skew partition. As a tool to complete this task we also develop a generalized 2-SAT algorithm, which by itself may have application to other partition problems. (c) 2006 Elsevier B.V. All rights reserved.

关键词： algorithms and data structures computational and structural complexity skew partition 2-SAT

来源：评论

学校读者我要写书评

暂无评论

The Boolean functions computed by random Boolean formulas OR how to grow the right function

引用

RANDOM STRUCTURES & ALGORITHMS 2005年第4期27卷 490-519页

作者： Brodsky, A Pippenger, N Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Univ British Columbia Dept Comp Sci Vancouver BC V5Z 1M9 Canada

We characterize growth processes (probabilistic amplification) by their initial conditions to derive conditions under which results such as Valiant's [J Algorithms 5 (1984), 363-366] hold. We completely characterize growth processes that use linear connectives and generalize Savick 's [Discrete Math 147 (1990), 95-103] analysis to characterize growth processes that use monotone connectives. Additionally, we obtain explicit bounds on the convergence rates of several growth processes, including the growth process studied in Savicky. (c) 2005 Wiley Periodicals, Inc.

关键词： computational and structural complexity growth processes probabilistic amplification random Boolean functions

来源：评论

学校读者我要写书评

暂无评论

On the ultimate complexity of factorials

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-3期326卷 419-429页

作者： Cheng, Q Univ Oklahoma Sch Comp Sci Norman OK 73019 USA

It has long been observed that certain factorization algorithms provide a way to write the product of many different integers succinctly. In this paper, we study the problem of representing the product of all integers from 1 to n (i.e. n!) by straight-line programs. Formally, we say that a sequence of integers a(n) is ultimately f(n)-computable, if there exists a nonzero integer sequence m(n) such that for any n, a(n)m(n) can be computed by a straight-line program (using only additions, subtractions and multiplications) of length at most f(n). Shub and Smale [12] showed that if n! is ultimately hard to compute, then the algebraic version of NP not equal P is true. Assuming a widely believed number theory conjecture concerning smooth numbers in a short interval, a subexponential upper bound (exp(crootlog n log log n)) for the ultimate complexity of n! is proved in this paper, and a randomized subexponential algorithm constructing such a short straight-line program is presented as well. (C) 2004 Elsevier B.V. All rights reserved.

关键词： computational and structural complexity

来源：评论

学校读者我要写书评

暂无评论

Deadlock prevention by acyclic orientations

引用

DISCRETE APPLIED MATHEMATICS 2003年第1期129卷 31-47页

作者： Bermond, JC Di Ianni, M Flammini, M Pérennès, S Univ Nice Sophia antipolis MASCOTTE Project I3S CNRS INRIA F-06902 Sophia Antipolis France Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy Univ Aquila Dipartimento Informat I-67100 Laquila Italy

Deadlock prevention for routing messages has a central role in communication networks, since it directly influences the correctness of parallel and distributed systems. In this paper, we extend some of the computational results presented in Second Colloquium on structural Information and Communication complexity (SIROCCO), Carleton University Press, 1995, pp. 1-12 on acyclic orientations for the determination of optimal deadlock-free routing schemes. In this context, minimizing the number of buffers needed to prevent deadlocks for a set of communication requests is related to finding an acyclic orientation of the network which minimizes the maximum number of changes of orientations on the dipaths realizing the communication requests. The corresponding value is called the rank of the set of dipaths. We first show that the problem of minimizing the rank is NP-hard if all shortest paths between the couples of nodes wishing to communicate have to be represented and even not approximable if only one shortest path between each couple has to tie represented. This last result holds even if we allow an error which is any sublinear function in the number of couples to be connected. We then improve some of the known lower and upper bounds on the rank of all possible shortest dipaths between any couple of vertices for particular topologies, such as grids and hypercubes, and we find tight results for tori. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： computational and structural complexity parallel algorithms routing and communication in interconnection networks

来源：评论

学校读者我要写书评

暂无评论

Strong reductions and immunity for exponential time

Strong reductions and immunity for exponential time

引用

20th Annual Symposium on Theoretical Aspects of Computer Science

作者： Schaefer, M Stephan, F Depaul Univ Sch CTI Chicago IL 60602 USA Heidelberg Univ Math Inst D-69120 Heidelberg Germany

ISBN: (纸本)3540006230

This paper investigates the relation between immunity and hardness in exponential time. The idea that these concepts are related originated in computability theory where it led to Post's program. It has been continued successfully in complexity theory [10,14,20]. We study three notions of immunity for exponential time. An infinite set A is called - EXP-immune, if it does not contain an infinite subset in EXP;- EXP-hyperimmune, if for every infinite sparse set B is an element of EXP and every polynomial p there is an x is an element of B such that {y is an element of B : p(-1) (\x\) less than or equal to \y\ less than or equal to p(\x\)} is disjoint from A;- EXP-avoiding, if the intersection A boolean AND B is finite for every sparse set B is an element of EXP. EXP-avoiding sets are always EXP-hyperimmune and EXP-hyperimmune sets are always EXP-immune but not vice versa. We analyze with respect to which polynomial-time reducibilities these sets can be hard for EXP. EXP-immune sets cannot be conjunctively hard for EXP although they can be hard for EXP with respect to disjunctive and parity-reducibility. EXP-hyperimmunes sets cannot be hard for EXP with respect to any of these three reducibilities. There is a relativized world in which there is an EXP-avoiding set which is hard with respect to positive truth-table reducibility. Furthermore, in every relativized world there is some EXP-avoiding set which is Turing-hard for EXP.

关键词： computational and structural complexity hardness for exponential time polynomial time reducibilities

来源：评论

学校读者我要写书评

暂无评论

Deadlock prevention by acyclic orientations

Deadlock prevention by acyclic orientations

引用

作者： Bermond, Jean-Claude Ianni, Miriam Di Flammini, Michele Pérennès, Stéphane MASCOTTE Project I3S-CNRS Université de Nice-Sophia Antipolis INRIA 2004 Route des Lucioles F-06902 Sophia-Antipolis cedex France Dipartimento di Matematica University of Rome Tor Vergata via della Ricerca Scientifica I-00133 Rome Italy Dipartimento di Informatica University of l'Aquila via Vetoio loc.Coppito I-67100 L'Aquila Italy

Deadlock prevention for routing messages has a central role in communication networks, since it directly influences the correctness of parallel and distributed systems. In this paper, we extend some of the computational results presented in Second Colloquium on structural Information and Communication complexity (SIROCCO), Carleton University Press, 1995, pp. 1-12 on acyclic orientations for the determination of optimal deadlock-free routing schemes. In this context, minimizing the number of buffers needed to prevent deadlocks for a set of communication requests is related to finding an acyclic orientation of the network which minimizes the maximum number of changes of orientations on the dipaths realizing the communication requests. The corresponding value is called the rank of the set of dipaths. We first show that the problem of minimizing the rank is NP-hard if all shortest paths between the couples of nodes wishing to communicate have to be represented and even not approximable if only one shortest path between each couple has to be represented. This last result holds even if we allow an error which is any sublinear function in the number of couples to be connected. We then improve some of the known lower and upper bounds on the rank of all possible shortest dipaths between any couple of vertices for particular topologies, such as grids and hypercubes, and we find tight results for tori. © 2002 Elsevier Science B.V. All rights reserved.

关键词： computational and structural complexity Parallel algorithms Routing and communication in interconnection networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：