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

SIAM JOURNAL ON COMPUTING 1991年第3期20卷 506-523页

作者： GOLDSMITH, J HEMACHANDRA, LA JOSEPH, D YOUNG, P UNIV WASHINGTON DEPT COMP SCI & ENGN SEATTLE WA 98195 USA UNIV ROCHESTER DEPT COMP SCI ROCHESTER NY 14627 USA UNIV WISCONSIN DEPT COMP SCI MADISON WI 53706 USA UNIV WISCONSIN DEPT MATH MADISON WI 53706 USA

In this paper a new property of sets, near-testability, is introduced. A set S is near-testable (S member-of NT) if the membership relation for all immediate neighbors is polynomially computable;i.e., if the function t(x) = chi-s(x) + chi-s(x - 1) (mod 2) is polynomially computable. The near-testable sets form a subclass of the class +P (parity polynomial time), introduced by Papadimitriou and Zachos, and Goldschlager and Parberry. +P has a complete set +SAT that has recently been shown by Valiant and Vazirani to be hard for NP under randomized polynomial-time reductions. It is proved that there is a uniform polynomial one-one reduction that takes every set in +P to a near-testable set, and it is shown that the image of +SAT under this reduction (which we call NTSAT) is polynomially isomorphic to +SAT. As corollaries it is shown that NTSAT is complete for both NT and for +P, that NTSAT is hard for NP under randomized polynomial-time reductions, and that the existence of one-way functions implies the existence of sets that are near-testable but not polynomially decidable. It is then asked whether near-testability is preserved under p-isomorphisms. This leads to a generalization, NT*, of NT similar to those introduced by Meyer and Paterson and by Ko for self-reducible sets. With this more general definition, NT* is shown to be closed under polynomial-time isomorphisms while remaining a subclass of +P. It is conjectured that it is a proper subclass. In fact it is shown that, relative to a random oracle, the containments P subset-or-is-equal-to NT subset-or-is-equal-to NT* subset-or-is-equal-to +P are proper with probability one. It is also shown that, relative to a random oracle, with probability one NT and NT* are incomparable with both NP and with coNP. Finally, the effects that the distribution and density of elements have on the complexity of near-testable sets are considered.

关键词： structural complexity theory NEAR-TESTABILITY ONE-WAY FUNCTIONS PARITY POLYNOMIAL TIME SELF-REDUCIBILITY

来源：评论

学校读者我要写书评

暂无评论

Downward separation fails catastrophically for limited nondeterminism classes

引用

SIAM JOURNAL ON COMPUTING 1998年第5期27卷 1420-1429页

作者： Beigel, R Goldsmith, J Lehigh Univ Dept Comp Sci & Elect Engn Packard Lab Bethlehem PA 18015 USA Yale Univ New Haven CT 06520 USA Univ Kentucky Dept Comp Sci Lexington KY 40506 USA

The beta hierarchy consists of classes beta(k) = NP[log(k) n] subset of or equal to NP. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the beta hierarchy do not seem to translate up, nor does closure under complement seem to cause the hierarchy to collapse. For any consistent set of collapses and separations of levels of the hierarchy that respects P = beta(1) subset of or equal to beta(2) subset of or equal to ... subset of or equal to NP, we can construct an oracle relative to which those collapses and separations hold;at the same time we can make distinct levels of the hierarchy closed under computation or not, as we wish. To give two relatively tame examples: for any k greater than or equal to 1, we construct an oracle relative to which P = beta(k) not equal beta(k+1) not equal beta(k+2) not equal ... and another oracle relative to which P = beta(k) not equal beta(k+1) = PSPACE. We also construct an oracle relative to which beta(2k) = beta(2k + 1) not equal beta(2k + 2) for all k.

关键词： structural complexity theory limited nondeterminism hierarchies oracles

来源：评论

学校读者我要写书评

暂无评论

Gaps, Ambiguity, and Establishing complexity-Class Containments via Iterative Constant-Setting

引用

ACM TRANSACTIONS ON COMPUTATION theory 2024年第4期16卷 1-26页

作者： Hemaspaandra, Lane A. Juvekar, Mandar Nadjimzadah, Arian Phillips, Patrick A. Univ Rochester Rochester NY 14627 USA Boston Univ Dept Comp Sci Boston MA 02215 USA UCLA Dept Math Los Angeles CA 90095 USA Gen Dynam Corp Reston VA 20190 USA

Cai and Hemachandra used iterative constant-setting to prove that Few c (R) P (and thus that FewP c (R) P). In this article, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed "nongappiness") of the easy-to-find "targets" used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorembased approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant's unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra-Pomerance-Wagstaff Conjecture implies that all (O(1) + log log n )-ambiguity NP sets are in the restricted counting class RC PRIMES .

关键词： structural complexity theory computational complexity theory ambiguity-limited NP restricted counting classes P-printable sets

来源：评论

学校读者我要写书评

暂无评论

The robustness of LWPP and WPP, with an application to graph reconstruction 43

The robustness of LWPP and WPP, with an application to graph...

引用

43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018

作者： Hemaspaandra, Edith Hemaspaandra, Lane A. Spakowski, Holger Watanabe, Osamu Rochester Institute of Technology RochesterNY United States University of Rochester RochesterNY United States University of Cape Town Rondebosch South Africa Tokyo Institute of Technology Tokyo Japan

ISBN: (纸本)9783959770866

We show that the counting class LWPP [8] remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques. The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i.e., PPLegitimate Deck = PP) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Köbler, Schöning, and Torán [15] that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard. We additionally show on the one hand that our main LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection- and acceptance-gap-value targets to simultaneously be polynomial-sized lists;yet on the other hand, we show that for the #P-based analog of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does. © Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, and Osamu Watanabe.

关键词： PP-lowness Robustness of counting classes structural complexity theory The legitimate deck problem The reconstruction conjecture

来源：评论

学校读者我要写书评

暂无评论

The opacity of backbones

引用

INFORMATION AND COMPUTATION 2021年 281卷 104772-104772页

作者： Hemaspaandra, Lane A. Narvaez, David E. Univ Rochester Dept Comp Sci Rochester NY 14627 USA

This paper uses structural complexity theory to study whether there is a chasm between knowing an object exists and getting one's hands on the object or its properties. In particular, we study the nontransparency of backbones. We show that, under the widely believed assumption that integer factoring is hard, there exist sets of boolean formulas that have obvious, nontrivial backbones yet finding the values of those backbones is intractable. We also show that, under the same assumption, there exist sets of boolean formulas that obviously have large backbones yet producing such a backbone is intractable. Furthermore, we show that if integer factoring is not merely worst-case hard but is frequently hard, as is widely believed, then the frequency of hardness in our two results is not too much less than that frequency. These results hold even if one's assumptions are, respectively, P = NP boolean AND coNP or that some NP boolean AND coNP problem is frequently hard. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Backbones Frequency of hardness NP boolean AND coNP structural complexity theory

来源：评论

学校读者我要写书评

暂无评论

BANISHING ROBUST TURING COMPLETENESS

引用

International Journal of Foundations of Computer Science 1993年第3期4卷 245-265页

作者： LANE A. HEMASPAANDRA SANJAY JAIN NIKOLAI K. VERESHCHAGIN Department of Computer Science University of Rochester Rochester New York 14627 USA Supported in part by a Hewlett-Packard Corporation equipment grant and by the National Science Foundation under grants CCR-8809174/CCR-8996198 CCR-8957604 and NSF-INT-9116781/JSPS-ENG-207. Institute of Systems Science National University of Singapore Singapore 0511 Republic of Singapore The Institute of New Technologies Kirovogradskaja 11 Moscow 113587 Russia

This paper proves that “promise classes” are so fragilely structured that they do not robustly (i.e. with respect to all oracles) possess Turinghard sets even in classes far larger than themselves. In particular, this paper shows that FewP does not robustly possess Turing hard sets for UP∩coUP and IP∩coIP does not robustly possess Turing hard sets for ZPP. It follows that ZPP, R, coR, UP∩coUP, UP, FewP∩coFewP, FewP, and IP∩coIP do not robustly possess Turing complete sets. This both resolves open questions of whether promise classes lacking robust downward closure under Turing reductions (e.g., R, UP, FewP) might robustly have Turing complete sets, and extends the range of classes known not to robustly contain many-one complete sets.

关键词： structural complexity theory Polynomial-time reductions Complete languages

来源：评论

学校读者我要写书评

暂无评论

ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS

引用

International Journal of Foundations of Computer Science 1991年第3期2卷 237-255页

作者： LANE A. HEMACHANDRA SANJAY JAIN Department of Computer Science University of Rochester Rochester NY 14627 USA Supported in part by the National Science Foundation under grant CCR-8809174/CCR-8996198 and Presidential Young Investigator Award CCR-8957604. Department of Computer and Information Sciences University of Delaware Newark DE 19716 USA Supported in part by the National Science Foundation under grant CCR-8320136. Work done in part while at the University of Rochester.

Polynomial-time positive reductions, as introduced by Selman, are by definition globally robust — they are positive with respect to all oracles. This paper studies the extent to which the theory of positive reductions remains intact when their global robustness assumption is removed. We note that two-sided locally robust positive reductions — reductions that are positive with respect to the oracle to which the reduction is made — are sufficient to retain all crucial properties of globally robust positive reductions. In contrast, we prove absolute and relativized results showing that one-sided local robustness fails to preserve fundamental properties of positive reductions, such as the downward closure of NP.

关键词： structural complexity theory Polynomial-time reductions complexity classes

来源：评论

学校读者我要写书评

暂无评论

THE ROBUSTNESS OF LWPP AND WPP, WITH AN APPLICATION TO GRAPH RECONSTRUCTION

引用

COMPUTATIONAL complexity 2020年第2期29卷 7-7页

作者： Hemaspaandra, Edith Hemaspaandra, Lane A. Spakowski, Holger Watanabe, Osamu Rochester Inst Technol Dept Comp Sci Rochester NY 14623 USA Univ Rochester Dept Comp Sci Rochester NY 14627 USA Univ Cape Town Dept Math & Appl Math ZA-7701 Rondebosch South Africa Tokyo Inst Technol Dept Math & Comp Sci Tokyo 1528552 Japan

We show that the counting class LWPP remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques. The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i.e., PPLegitimate Deck = PP) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Kobler, Schoning & Toran that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard. We additionally show on the one hand that our LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection and acceptance gap-value targets to simultaneously be polynomial-sized lists;yet on the other hand, we show that for the #P-based analogue of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does. Despite that nonrobustness result for a #P-based class, we show that the #P-based "exact counting" class C=P remains unchanged even if one allows a polynomial number of target values for the number of accepting paths of the machine.

关键词： structural complexity theory Robustness of counting classes The legitimate deck problem PP-lowness The Reconstruction Conjecture

来源：评论

学校读者我要写书评

暂无评论

Search versus Decision for Election Manipulation Problems

引用

ACM TRANSACTIONS ON COMPUTATION theory 2020年第1期12卷 3-3页

作者： Hemaspaandra, Edith Hemaspaandra, Lane A. Menton, Curtis Rochester Inst Technol Dept Comp Sci Rochester NY 14623 USA Univ Rochester Dept Comp Sci Rochester NY 14627 USA Google Inc Mountain View CA 94043 USA

Most theoretical definitions about the complexity of manipulating elections focus on the decision problem of recognizing which instances can be successfully manipulated rather than the search problem of finding the, successful manipulative actions. Since the latter is a far more natural goal for manipulators, that definitional focus may be misguided if these two complexities can differ. Our main result is that they probably do differ: If P not equal NP boolean AND coNP (Which itself is well known to hold if integer factoring is hard), then for election manipulation, election bribery, and sonic types of election control, there are election systems for which the problem of recognizing which instances can be successfully manipulated is polynomial-time solvable, yet the task of producing the successful manipulations cannot be done in polynomial time.

关键词： structural complexity theory search versus decision borodin-demers theorem NP intersect coNP elections typical-case complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：