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

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 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

SAVING QUERIES WITH RANDOMNESS

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 1995年第3期50卷 476-492页

作者： ROHATGI, P CORNELL UNIV DEPT COMP SCI ITHACA NY 14853 USA

In this paper, we investigate the power of randomness to save a query to an NP-complete set. We show that the P-SATI[k] less than or equal to(m)(p)-complete language randomly reduces to a language in P-SATI[k-1] with a one-sided error probability of 1/[k/2] or a two sided-error probability of 1/(k+1). Furthermore, we prove that these probability bounds are tight;i.e., they cannot be improved by 1/poly, unless PH collapses. We also obtain tight performance bounds for randomized reductions between nearby classes in the boolean and bounded query hierarchies. These bounds provide probability thresholds for completeness under randomized reductions in these classes. Using these thresholds, we show that certain languages in the boolean hierarchy which are not less than or equal to(m)(p)-complete in some relativized worlds, nevertheless inherit many of the hardness properties associated with the less than or equal to(m)(p)-complete languages. Finally, we explore the relationship between randomization and functions that are computable using bounded queries to SAT. For any function h(n) = O(log n), we show that there is a function f computable using h(nj nonadaptive queries to SAT, which cannot be computed correctly with probability 1/2+1/poly by any randomized machine which makes less than h(n) adaptive queries to any oracle, unless PH collapses. (C) 1995 Academic Press, Inc.

关键词： boolean hierarchy Cheatable sets Bi-immunity Np Complexity Complexity Social hierarchy Error probability PH Threshold Bound North Pacific Pattern Language hardness property

来源：评论

学校读者我要写书评

暂无评论

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... 详细信息; 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 (e.g., queries made during truth-table reductions). Very different kinds of such restrictions result in the same or comparable complexity classes. In particular, the class $P^{NP} [O (\log n)]$; 来源：评论; 学校读者我要写书评

暂无评论

On the query complexity of clique size and maximum satisfiability

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 1996年第2期53卷 298-313页

作者： Chang, R Department of Computer Science and Electrical Engineering University of Maryland Baltimore County Baltimore Maryland 21228 USA

This paper explores the bounded query complexity of approximating the size of the maximum clique in a graph (Clique Size) and the number of simultaneously satisfiable clauses in a BCNF formula (MaxSat). The results in the paper show that for certain approximation factors, approximating Clique Size and MaxSat are complete for corresponding bounded query classes under metric reductions. The completeness result is important because it shows that queries and approximation are interchangeable: NP queries can be used to solve NP-approximation problems and solutions to NP-approximation problems answer queries to NP oracles. Completeness also shows the existence of approximation preserving reductions from many NP-approximation problems to approximating Clique Size and MaxSat (e.g., from approximating Chromatic Number to approximating Clique Size). Since query complexity is a quantitative complexity measure, these results also provide a framework for comparing the complexities of approximating Clique Size and approximating MaxSat. In addition, this paper examines the query complexity of the minimization version of the satisfiability problem, MinUnsat, and shows that the complexity of approximating MinUnsat is very similar to the complexity of approximating Clique Size, Since MaxSat and MinUnsat share the same solution space, the ''approximability'' of MaxSat is not due to the intrinsic complexity of satisfiability, but is an artifact of viewing the approximation version of satisfiability as a maximization problem. (C) 1996 Academic Press, Inc.

关键词： boolean hierarchy Bounded queries Approximation Optimization Complexity approximation computability

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A note on parallel queries and the symmetric-difference hierarchy

引用

INFORMATION PROCESSING LETTERS 1998年第1期66卷 13-20页

作者： Wagner, KW Univ Wurzburg Lehrstuhl Theoret Informat D-97072 Wurzburg Germany

For classes K-1, K-2,...,K-m of languages and m, r(1), r(2),..., r(m) greater than or equal to 1 let the class P-parallel to(K1[r1],K2[r2],...,Km[rm]) be defined as the class of languages which can be accepted by a deterministic polynomial time machine which makes (simultaneously for j = 1, 2,..., m) r(j) parallel queries to an oracle B-j epsilon K-j For classes K-1, K-2,...,K-m epsilon{Sigma(1)(P) Sigma(2)(P) Sigma(3)(P),...} of the polynomial time hierarchy we prove P-parallel to(K1[r1],K2[r2],...,Km[rm])=P+K-1+>...+K-1+K-2+...+K-m+...+K-m where K+M = (def) {A Delta B: A epsilon K and B epsilon M} (K-j appears r(j) times). Hence the classes of the form P parallel to(K1[r1],K2[r2],...,Km[rm]) are exactly the classes of Selivanov's plus hierarchy when the term P+ is added. This result is valid also for a large variety of other families of classes. Finally, applications to query order classes from Hemaspaandra et al. (1997) and Beigel and Chang (1997) are given. (C) 1998 Elsevier Science B.V.

关键词： boolean hierarchy symmetric-difference hierarchy plus hierarchy parallel queries query order

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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