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

The boolean hierarchy and the polynomial hierarchy: A closer connection

SIAM JOURNAL ON COMPUTING 1996年第2期25卷 340-354页

作者： Chang, R Kadin, J CORNELL UNIV DEPT COMP SCIITHACANY 14853 UNIV MAINE DEPT COMP SCIORONOME 04469

We show that if the boolean hierarchy collapses to level k, then the polynomial hierarchy collapses to BH3(k), where BH3(k) is the kth level of the boolean hierarchy over Sigma(2)(P). This is an improvement over the known results, which show that the polynomial hierarchy would collapse to (PO)-O-NPNP[(log n)]. This result is significant in two ways. First, the theorem says that a deeper collapse of the boolean hierarchy implies a deeper collapse of the polynomial hierarchy. Also, this result points to some previously unexplored connections between the boolean and query hierarchies of Delta(2)(P) and Delta(3)(P). Namely, BH(k) = co-BH(k) double right arrow BH3(k) = co-BH3(k), P(NP)parallel to[k] = P(NP)parallel to[k+1] double right arrow P-NPNP parallel to[k+1] = P-NPNP parallel to[k+2].

关键词： polynomial-time hierarchy boolean hierarchy polynomial-time Turing reductions oracle access nonuniform algorithms sparse sets

来源：评论

学校读者我要写书评

暂无评论

The boolean hierarchy of NP-partitions

引用

INFORMATION AND COMPUTATION 2008年第5期206卷 538-568页

作者： Kosub, Sven Wagner, Klaus W. Tech Univ Munich Fac Informat D-85748 Munich Germany Univ Wurzburg D-97074 Wurzburg Germany

We introduce the boolean hierarchy of k-partitions over NP for k >= 3 as a generalization of the boolean hierarchy of sets (i.e., 2-partitions) over NP. Whereas the structure of the latter hierarchy is rather simple the structure of the boolean hierarchy of k-partitions over NP for k >= 3 turns out to be much more complicated. We formulate the Embedding Conjecture which enables us to get a complete idea of this structure. This conjecture is supported by several partial results. (c) 2007 Elsevier Inc. All rights reserved.

关键词： computational complexity theory partitions boolean hierarchy polynomial hierarchy orders and lattices

来源：评论

学校读者我要写书评

暂无评论

THE POLYNOMIAL-TIME hierarchy COLLAPSES IF THE boolean hierarchy COLLAPSES: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1988年第6期17卷 1263-1282页; 作者： KADIN, J Cornell Univ NY United States; It is shown that if the boolean hierarchy (BH) collapses, then there exists a sparse set S such that co-NP⊆ NPS<span style=; It is shown that if the boolean hierarchy (BH) collapses, then there exists a sparse set S such that $co-NP \subseteq {NP}^{S}$; 关键词： 68Q15 03D15 03D20 polynomial time hierarchy boolean hierarchy polynomial time Turing reductions oracle access nonuniform algorithms sparse sets; 来源：评论; 学校读者我要写书评

暂无评论

THE boolean hierarchy .1. STRUCTURAL-PROPERTIES

引用

SIAM JOURNAL ON COMPUTING 1988年第6期17卷 1232-1252页

作者： CAI, JY GUNDERMANN, T HARTMANIS, J HEMACHANDRA, LA SEWELSON, V WAGNER, K WECHSUNG, G CORNELL UNIV DEPT COMP SCIITHACANY 14853 FRIEDRICH SCHILLER UNIV MATH SECTDDR-6900 JENAGER DEM REP DARTMOUTH COLL DEPT MATH & COMP SCIHANOVERNH 03755 UNIV AUGSBURG INST MATHD-8900 AUGSBURGFED REP GER

In this paper, we study the complexity of sets formed by boolean operations (union, intersection, and complement) on NP sets. These are the sets accepted by trees of hardware with NP predicates as leaves, and together... 详细信息

关键词： 68Q15 03D15 polynomial-time hierarchy boolean hierarchy relativized complexity classes oracles immunity complete languages structural complexity

来源：评论

学校读者我要写书评

暂无评论

THE boolean hierarchy .2. APPLICATIONS

引用

SIAM JOURNAL ON COMPUTING 1989年第1期18卷 95-111页

The boolean hierarchy I: Structural Properties [J. Cai et al., SIAM J. Comput ., 17 (1988), pp. 1232–252] explores the structure of the boolean hierarchy, the closure of NP with respect to boolean operations. This paper uses the boolean hierarchy as a tool with which to extend and explain three important results in structural complexity theory.

关键词： 68Q15 03D15 sparse sets counting classes circuits boolean hierarchy structural complexity theory polynomial-time hierarchy relativized complexity classes

来源：评论

学校读者我要写书评

暂无评论

Exact complexity of Exact-Four-Colorability

引用

INFORMATION PROCESSING LETTERS 2003年第1期87卷 7-12页

作者： Rothe, J Univ Dusseldorf Abt Informat D-40225 Dusseldorf Germany

Let M-k be a given set of k integers. Define Exact-M-k-Colorability to be the problem of determining whether or not chi(G), the chromatic number of a given graph G, equals one of the k elements of the set M-k exactly. In 1987, Wagner [Theoret. Comput. Sci. 51 (1987) 53-80] proved that Exact-Mk-Colorability is BH2k (NP)-complete, where M-k = {6k + 1, 6k + 3,...,8k - 1} and BH2k (NP) is the 2kth level of the boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not chi(G) = 7, where DP = BH2 (NP). Wagner raised the question of how small the numbers in a k-element set M-k can be chosen such that Exact-Mk-Colorability still is BH2k (NP) -complete. In particular. for k = 1. he asked if it is DP-complete to determine whether or not chi(G) = 4. In this note, we solve Wagner's question and prove the optimal result: For each k greater than or equal to 1, Exact-M-k-Colorability is BH2k (NP)-complete for M-k = {3k + 1, 3k + 3,...,5k - 1}. In particular, for k = 1, we determine the precise threshold of the parameter t is an element of {4. 5. 6. 7} for which the problem Exact-{t}-Colorability jumps from NP to DP-completeness: It is DP-complete to determine whether or not chi(G) = 4, yet Exact-(3)-Colorability is in NP. (C) 2003 Elsevier Science B.V. All rights reserved.

关键词： computational complexity graph colorability completeness boolean hierarchy

来源：评论

学校读者我要写书评

暂无评论

Observations on complete sets between linear time and polynomial time

引用

INFORMATION AND COMPUTATION 2011年第2期209卷 173-182页

作者： Hemmerling, Armin Ernst Moritz Arndt Univ Greifswald Inst Math & Informat D-17487 Greifswald Germany

There is a single set that is complete for a variety of nondeterministic time complexity classes with respect to related versions of m-reducibility. This observation immediately leads to transfer results for determinism versus nondeterminism solutions. Also, an upward transfer of collapses of certain oracle hierarchies, built analogously to the polynomial-time or the linear-time hierarchies, can be shown by means of uniformly constructed sets that are complete for related levels of all these hierarchies. A similar result holds for difference hierarchies over nondeterministic complexity classes. Finally, we give an oracle set relative to which the nondeterministic classes coincide with the deterministic ones, for several sets of time bounds, and we prove that the strictness of the tape-number hierarchy for deterministic linear-time Turing machines does not relativize. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Many-one reducibility Completeness Determinism versus nondeterminism Polynomial-time hierarchy Linear-time hierarchy boolean hierarchy

来源：评论

学校读者我要写书评

暂无评论

BOUNDED QUERY CLASSES: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1990年第5期19卷 833-846页; 作者： WAGNER, KW Univ Wuerzburg Wuerzburg Germany; Polynomial time machines having restricted access to an NP oracle are investigated. Restricted access means that the number of queries to the oracle is restricted or the way in which the queries are made is restricted... 详细信息

FUNCTION OPERATORS SPANNING THE ARITHMETICAL AND THE POLYNOMIAL hierarchy

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2010年第3期44卷 379-418页

作者： Hemmerling, Armin Ernst Moritz Arndt Univ Greifswald Inst Math & Informat D-17487 Greifswald Germany

A modified version of the classical mu-operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability and complexity theory. The close relationships between nesting levels of operators and the stratification of the hierarchy also hold for suitable restrictions of the operators with respect to the polynomial hierarchy if one starts with the polynomial-time computable functions. It follows that questions around P vs. NP and NP vs. coNP can equivalently be expressed by closure properties of function classes under these operators. The polytime version of the first value operator can be used to establish hierarchies between certain consecutive levels within the polynomial hierarchy of functions, which are related to generalizations of the boolean hierarchies over the classes Sigma(p)(k).

关键词： Arithmetical hierarchy polynomial hierarchy boolean hierarchy P versus NP NP versus coNP first value operator minimalization inversion of functions

来源：评论

学校读者我要写书评

暂无评论

ON THE STRUCTURE OF BOUNDED QUERIES TO ARBITRARY NP SETS

引用

SIAM JOURNAL ON COMPUTING 1992年第4期21卷 743-754页

作者： CHANG, R Cornell Univ Ithaca NY United States

Kadin [SIAM J. Comput., 17 (1988), pp. 1263-1282] showed that if the polynomial hierarchy (PH) has infinitely many levels, then for all k, P(SAT[k]) subset-of P(SAT[k+1]). This paper extends Kadin's technique and shows that a proper query hierarchy is not an exclusive property of NP complete sets. In fact, for any A is-an-element-of NP - low3, if PH h. infinitely many levels, then p(A[k]) subset-of p(A[k+1]). Moreover, for the case of parallel queries, p(A parallel-to [k+1]) is not even contained in P(SAT parallel-to [k]). These same techniques can be used to explore some other questions about query hierarchies. For example, if there exists any A such that p(A[2]) = p(SAT[1]), then PH collapses to DELTA-3P.

关键词： POLYNOMIAL-TIME hierarchy boolean hierarchy BOUNDED QUERIES SPARSE SETS NONUNIFORM COMPUTATION

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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