The Complexity of Finding Top-Toda-Equivalence-Class Members期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

The Complexity of Finding Top-Toda-Equivalence-Class Members

Authors:	Lane A Hemaspaandra Mitsunori Ogihara Mohammed J Zaki Marius Zimand

Affiliation:	(1) Department of Computer Science, University of Rochester, Rochester, NY 14627, USA;(2) Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 12180, USA;(3) Department of Computer and Information Sciences, Towson University, Towson, MD 21252, USA

Abstract:	We identify two properties that for P-selective sets are effectively computable. Namely, we show that, for any P-selective set, finding a string that is in a given length's top Toda equivalence class (very informally put, a string from $\Sigma^n$ that the set's P-selector function declares to be most likely to belong to the set) is ${\rm FP}^{\Sigma^p_2}$ computable, and we show that each P-selective set contains a weakly- $P^{\Sigma^p_2}$ -rankable subset.

Keywords:
本文献已被 SpringerLink 等数据库收录！