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

counting complexity classes for numeric computations II:: Algebraic and semialgebraic sets

JOURNAL OF complexity 2006年第2期22卷 147-191页

作者： Bürgisser, P Cucker, F City Univ Hong Kong Dept Math Kowloon Hong Kong Peoples R China Paderborn Univ Dept Math D-33095 Paderborn Germany

We define counting classes #P-R and #P-C in the Blum-Shub-Smale setting Of Computations over the real or complex numbers, respectively. The problems of counting the number of solutions of systems of polynomial inequalities over R, or of systems of polynomial equalities over C, respectively, turn out to be natural complete problems in these classes. We investigate to what extent the new counting classes capture the complexity of computing basic topological invariants of semialgebraic sets (over R) and algebraic sets (over C). We prove that the problem of computing the Euler-Yao characteristic of semialgebraic sets is FP#(PR)-complete, and that the problem of computing the geometric degree of complex algebraic sets is FP#(RPC)(C) -complete. We also define new counting complexity classes in the classical Turing model via taking FPC complete. We, Boolean parts of the classes above, and show that the problems to compute the Euler characteristic and the geometric degree of (semi)algebraic sets given by integer polynomials are complete in these classes. We complement the results in the Turing model by proving, for all k is an element of N, the FPSPAGE-hardness of the problem of computing the kth Betti number ofthe set of real zeros of a given integer polynomial. This holds with respect to the singular homology as well as for the Borel-Moore homology. (c) 2005 Elsevier Inc. All rights reserved.

关键词： counting complexity real complexity classes geometric degree Euler characteristic Betti numbers

来源：评论

学校读者我要写书评

暂无评论

counting complexity of propositional abduction

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2010年第7期76卷 634-649页

作者： Hermann, Miki Pichler, Reinhard Ecole Polytech LIX CNRS UMR 7161 F-91128 Palaiseau France Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria

Abduction is an important method of non-monotonic reasoning with many applications in artificial intelligence and related topics. In this paper, we concentrate on propositional abduction, where the background knowledge is given by a propositional formula. Decision problems of great interest are the existence and the relevance problems. The complexity of these decision problems has been systematically studied while the counting complexity of propositional abduction has remained obscure. The goal of this work is to provide a comprehensive analysis of the counting complexity of propositional abduction in various settings. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Computational complexity counting complexity Propositional abduction Horn Definite Horn Dual Horn Bijunctive formulas

来源：评论

学校读者我要写书评

暂无评论

counting complexity of Reachability Problem for Boolean Control Networks with Free Control Sequence 41

Counting Complexity of Reachability Problem for Boolean Cont...

引用

第41届中国控制会议

作者： Zhi Li Hongsheng Qi School of Mathematical Sciences University of Chinese Academy of Sciences Key Laboratory of Systems and Control Institute of Systems ScienceAcademy of Mathematics and Systems ScienceChinese Academy of Sciences

ISBN: (数字)9789887581536

ISBN: (纸本)9781665482561

In this paper,we investigate the counting complexity of reachability problem for Boolean control networks(BCNs) by Boolean counting constraint satisfaction problem(#CSP).We prove that the counting complexity of a class of Boolean#CSP by using Post's lattice in universal algebra is#P-complete,and further use it to classify the counting complexity of M-reachability problem(#M-RP) when M=***,we prove that #M-RP is #P-complete.

关键词： #CSP Boolean Control Network counting complexity Reachability

来源：评论

学校读者我要写书评

暂无评论

Block interpolation: A framework for tight exponential-time counting complexity

引用

INFORMATION AND COMPUTATION 2018年第Part2期261卷 265-280页

作者： Curticapean, Radu Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Kende U 13-17 Budapest Hungary

We devise a framework for proving tight lower bounds under the counting exponentialtime hypothesis # ETHintroduced by Delletal.(2014) [18]. Our framework allows us to convert classical # P-hardness results for counting problems into tight lower bounds under # ETH, thus ruling out algorithms with running time 2(o(n)) on graphs with nvertices and O(n) edges. As exemplary applications of this framework, we obtain tight lower bounds under # ETHfor the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for one line. This remaining line was settled very recently by Brand etal.(2016) [24]. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Exponential-time hypothesis counting complexity Permanent Matching polynomial Independent set polynomial Tutte polynomial

来源：评论

学校读者我要写书评

暂无评论

On the counting complexity of propositional circumscription

引用

INFORMATION PROCESSING LETTERS 2008年第4期106卷 164-170页

作者： Durand, Arnaud Hermann, Miki Ecole Polytech LIX CNRS UMR 7161 F-91128 Palaiseau France Univ Denis Diderot Paris 7 Equipe Log Math UMR 7056 F-75251 Paris 05 France

Propositional circumscription, asking for the minimal models of a Boolean formula, is an important problem in artificial intelligence, in data mining, in coding theory, and in the model checking based procedures in automated reasoning. We consider the counting problems of propositional circumscription for several subclasses with respect to the structure of the formula. We prove that the counting problem of propositional circumscription for dual Horn, bijunctive, and affine formulas is #P-complete for a particular case of Turing reduction, whereas for Horn and 2affine formulas it is in FP. As a corollary, we obtain also the #P-completeness result for the counting problem of hypergraph transversal. (c) 2007 Elsevier B.V. All rights reserved.

关键词： computational complexity counting complexity propositional circumscription Horn dual Horn bijunctive and affine formulas hypergraph transversal

来源：评论

学校读者我要写书评

暂无评论

Subtractive reductions and complete problems for counting complexity classes

引用

THEORETICAL COMPUTER SCIENCE 2005年第3期340卷 496-513页

作者： Durand, A Hermann, M Kolaitis, PG Ecole Polytech CNRS UMR 7161 LIX F-91128 Palaiseau France Univ Paris 12 LACL Dept Comp Sci F-94010 Creteil France Univ Calif Santa Cruz Dept Comp Sci Santa Cruz CA 95064 USA

We introduce and investigate a new type of reductions between counting problems, which we call subtractive reductions. We show that the main counting complexity classes #P, #NP, as well as all higher counting complexity classes # (.) Pi P-k, k >= 2, are closed under subtractive reductions. We then pursue problems that are complete for these classes via subtractive reductions. We focus on the class #NP (which is the same as the class # (.) coNP) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a Boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear Diophantine inequalities. (c) 2005 Elsevier B.V. All rights reserved.

关键词： counting complexity complete problems subtractive reductions

来源：评论

学校读者我要写书评

暂无评论

counting complexity classes for numeric computations I:: Semilinear sets

引用

SIAM JOURNAL ON COMPUTING 2003年第1期33卷 227-260页

作者： Bürgisser, P Cucker, F Paderborn Univ Fac Comp Sci Elect Engn & Math D-33095 Paderborn Germany City Univ Hong Kong Dept Math Kowloon Hong Kong Peoples R China

We de. ne a counting class #P-add in the Blum-Shub-Smale setting of additive computations over the reals. Structural properties of this class are studied, including a characterization in terms of the classical counting class #P introduced by Valiant. We also establish transfer theorems for both directions between the real additive and the discrete setting. Then we characterize in terms of completeness results the complexity of computing basic topological invariants of semilinear sets given by additive circuits. It turns out that the computation of the Euler characteristic is FPadd#Padd-complete, while for fixed k the computation of the kth Betti number is FPAR(add)-complete. Thus the latter is more difficult under standard complexity theoretic assumptions. We use all of the above to prove some analogous completeness results in the classical setting.

关键词： counting complexity real complexity classes Euler characteristic Betti numbers

来源：评论

学校读者我要写书评

暂无评论

Subtractive reductions and complete problems for counting complexity classes 25th

引用

25th Conference on Mathematical Foundations of Computer Science

ISBN: (纸本)3540679014

关键词： counting complexity complete problems subtractive reductions

来源：评论

学校读者我要写书评

暂无评论

complexity of counting the optimal solutions

引用

THEORETICAL COMPUTER SCIENCE 2009年第38-40期410卷 3814-3825页

作者： Hermann, Miki Pichler, Reinhard Ecole Polytech CNRS LIX UMR 7161 F-91128 Palaiseau France Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria

Following the approach of Hemaspaandra and Vollmer, we can define counting complexity classes #.C for any complexity class C of decision problems. In particular, the classes#. Pi(k)P with k >= 1 corresponding to all levels of the polynomial hierarchy, have thus been studied. However, for a large variety of counting problems arising from optimization problems, a precise complexity classification turns out to be impossible with these classes. In order to remedy this unsatisfactory situation, we introduce a hierarchy of new counting complexity classes # . Opt(k)P and # . Opt(k)P[log n] with k >= 1. We prove several important properties of these new classes, like closure properties and the relationship with the # . Pi(k)P-classes. Moreover, we establish the completeness of several natural counting complexity problems for these new classes. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Computational complexity counting complexity Optimization problems

来源：评论

学校读者我要写书评

暂无评论

The parameterised complexity of counting connected subgraphs and graph motifs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2015年第4期81卷 702-716页

作者： Jerrum, Mark Meeks, Kitty Queen Mary Univ London Sch Math Sci London E1 4NS England

We introduce a family of parameterised counting problems on graphs, p-#INDUCED SUBGRAPH WITH PROPERTY(Phi), which generalises a number of problems which have previously been studied. This paper focuses on the case in which Phi defines a family of graphs whose edge-minimal elements all have bounded treewidth;this includes the special case in which Phi describes the property of being connected. We show that exactly counting the number of connected induced k-vertex subgraphs in an n-vertex graph is #W[1]-hard, but on the other hand there exists an FPTRAS for the problem;more generally, we show that there exists an FPTRAS for p-#INDUCED SUBGRAPH WITH PROPERTY(Phi) whenever Phi is monotone and all the minimal graphs satisfying Phi have bounded treewidth. We then apply these results to a counting version of the GRAPH MOTIF problem. (C) 2014 Elsevier Inc. All rights reserved.

关键词： counting complexity Parameterised complexity FPTRAS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：