AbstractWe show that if SAT is quasi-linear truth-table reducible to a p-selective set then NP = P. As a consequence it follows that for a class K ϵ {PP,C = P}, if every set in K is quasi-linear truth-table reducible to a p-selective set then K = P
We study whether sets inside NP can be reduced to sets with low information content but possibly sti...
We distinguish self-reducibility of a language L with the question of whether search reduces to deci...
We study the consequences of NP having non-uniform polynomial size circuits of various types. We con...
We make an elaborate analysis of the intervals defined by the ordered list of queries to the p-selec...
AbstractWe show that any p-selective and self-reducible set is in P. As the converse is also true, w...
AbstractSelf-reducible sets and some low sets, including p-selective sets, and weakly p-selective se...
Ogiwara and Watanabe showed that if SAT is bounded truth-table reducible to a sparse set, then P = N...
AbstractWe distinguish self-reducibility of a languageLwith the question of whether search reduces t...
We show that if every NP set is ≤ P btt -reducible to some P-selective set, then NP is contained...
A set is P-selective if there is a polynomial-time semi-decision algorithm for the set---an algorith...
AbstractA set is P-selective (Selman, 1979) if there is a polynomial-time semidecision algorithm for...
We study two properties of a complexity class —whether there exists a truthtable hard p-selective la...
A set is P-selective if there is a polynomial-time semi-decision algorithm for the set---an algorith...
Much structural work on NP-complete sets has exploited SAT's d-self-reducibility. In this paper...
] Ashish V. Naik Alan L. Selman y December 19, 1995 Abstract We study two properties of a compl...
We study whether sets inside NP can be reduced to sets with low information content but possibly sti...
We distinguish self-reducibility of a language L with the question of whether search reduces to deci...
We study the consequences of NP having non-uniform polynomial size circuits of various types. We con...
We make an elaborate analysis of the intervals defined by the ordered list of queries to the p-selec...
AbstractWe show that any p-selective and self-reducible set is in P. As the converse is also true, w...
AbstractSelf-reducible sets and some low sets, including p-selective sets, and weakly p-selective se...
Ogiwara and Watanabe showed that if SAT is bounded truth-table reducible to a sparse set, then P = N...
AbstractWe distinguish self-reducibility of a languageLwith the question of whether search reduces t...
We show that if every NP set is ≤ P btt -reducible to some P-selective set, then NP is contained...
A set is P-selective if there is a polynomial-time semi-decision algorithm for the set---an algorith...
AbstractA set is P-selective (Selman, 1979) if there is a polynomial-time semidecision algorithm for...
We study two properties of a complexity class —whether there exists a truthtable hard p-selective la...
A set is P-selective if there is a polynomial-time semi-decision algorithm for the set---an algorith...
Much structural work on NP-complete sets has exploited SAT's d-self-reducibility. In this paper...
] Ashish V. Naik Alan L. Selman y December 19, 1995 Abstract We study two properties of a compl...
We study whether sets inside NP can be reduced to sets with low information content but possibly sti...
We distinguish self-reducibility of a language L with the question of whether search reduces to deci...
We study the consequences of NP having non-uniform polynomial size circuits of various types. We con...
DOI
Add to ORKG