期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that the class of sets which can be polynomial
time truth table reduced to some p-superterse sets has
p-measure 0. Hence, no P-selective set is ptt-hard
for E. Also we give a partial affirmative answer to
the conjecture by Beigel, Kummer and Stephan. They conjectured
that every ptt-hard set for NP is P-superterse
unless P=NP. We will prove that every ptt-hard set
for NP is P-superterse unless NP has p-measure 0.
