# P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP

@inproceedings{Selman1979PSelectiveST, title={P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP}, author={Alan L. Selman}, booktitle={ICALP}, year={1979} }

The notion of p-selective sets, and tally languages, are used to study polynomial time reducibilities on NP. P-selectivity has the property that a set A belongs to the class P if and only if both A NP A and A is p-selective. We prove that for m every tally language set in NP there exists a polynomial time equivalent set in NP that is p-selective. From this result it follows that if NEXT ~ DEXT , then polynomial time Turing and many-one reducibilities differ on NP.

#### Topics from this paper

#### 140 Citations

On sets turing reducible to p-selective sets

- Computer Science, Mathematics
- Theory of Computing Systems
- 2007

It is shown that EXP cannot be reduced to the p-selective sets under 2lin time reductions with at mostnk queries for any fixed k ε N. Expand

Selectivity: Reductions, Nondeterminism, and Function Classes 1

- 1993

A set is P-selective [Sel79] if there is a polynomial-time semi-decision algorithm for the set|an algorithm that given any two strings decides which is \more likely" to be in the set. This paper… Expand

Polynomial-Time Semi-Rankable Sets

- Mathematics
- 1996

We study the polynomial-time semi-rankable sets (P-sr), the ranking analog of the P-selective sets. We prove that P-sr is a strict subset of the P-selective sets, and indeed that the two classes… Expand

Polynomial-Time Semi-Rankable

- 1995

We study the polynomial-time semi-rankable sets (P-sr), the ranking analog of the P-selective sets. We prove that P-sr is a strict subset of the P-selective sets, and indeed that the two classes… Expand

On Self-Reducibility and Weak P-Selectivity

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1983

It is proved that self-reducible sets are not polynomial-time Turing reducible to these sets, and weakly p -selective sets are introduced as a generalization of p - selective sets based on this characterization. Expand

Nondeterministically Selective Sets

- Mathematics, Computer Science
- Int. J. Found. Comput. Sci.
- 1995

NP-selective sets (formally, sets that are selective via NPSVt functions) are studied as a natural generalization of P-selectives, and it is shown that, assuming P≠NP∩coNP, the class of NP- selective sets properly contains the class that is implicit in Karp and Lipton’s seminal result on nonuniform classes. Expand

Selectivity and Self-reducibility: New Characterizations of Complexity Classes

- 1994

It is known that a set is in P ii it is p-time Turing self-reducible and p-selective 2] and a p-time Turing self-reducible set is in NP \ coNP ii it is NP-selective 4]. We generalize these new… Expand

Approximable sets

- Computer Science
- Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory
- 1994

In a relativized world, a d-self-reducible set in NP-P is constructed that is polynomial-time 2-tt reducible to a p-selective set, and no easily countable set is NP-hard under Turing reductions unless P=NP. Expand

Analogues of Semicursive Sets and Effective Reducibilities to the Study of NP Complexity

- Computer Science, Mathematics
- Inf. Control.
- 1982

The structure of NP <~-degrees is similar to the one of r, and the reducibilities formulated by Cook (1971) and Karp (1973) are just the restrictions to polynomial time of Turing and many-one reducibility, respectively. Expand

Approximable Sets Universitt at Karlsruhe

- 1994

Much structural work on NP-complete sets has exploited SAT's d-self-reduci-bility. In this paper we exploit the additional fact that SAT is a d-cylinder to show that NP-complete sets are p-superterse… Expand

#### References

SHOWING 1-10 OF 13 REFERENCES

On the Structure of Polynomial Time Reducibility

- Mathematics, Computer Science
- JACM
- 1975

The method of showing density ymlds the result that if P ~ NP then there are members of NP -P that are not polynomml complete is shown, which means there is a strictly ascending sequence with a minimal pair of upper bounds to the sequence. Expand

Relationship Between Density and Deterministic Complexity of NP-Complete Languages

- Computer Science
- ICALP
- 1978

The main theorem of this paper establishes that if CLIQUE has some f-sparse translation into another set, which is calculable by a deterministic Turing machine in time bounded by f, then all the sets belonging to NP are calculable in time bound by a function polynomially related to f. Expand

On Languages Accepted in Polynomial Time

- Mathematics, Computer Science
- SIAM J. Comput.
- 1972

The family NP (P) of languages accepted by nondeterministic (deterministic) Turing machines operating in polynomial time is distinct from many well-known families of languages defined by tape-bounded… Expand

Tally Languages and Complexity Classes

- Computer Science
- Inf. Control.
- 1974

The following statements are shown to be equivalent: (i) Every language accepted by a nondeterministic Turing machine which operates within time bound 2 cn for some c > 0 is also accepted by a… Expand

Comparing Complexity Classes

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1974

The results do not establish the existence of possible relationships between these classes; rather, they show the consequences of such relationships, in some cases offering circumstantial evidence that these relationships do not hold and that certain pairs of classes are set-theoretically incomparable. Expand

The complexity of theorem-proving procedures

- Computer Science, Mathematics
- STOC
- 1971

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a… Expand

Turing Machines and the Spectra of First-Order Formulas

- Computer Science
- 1974

It is shown that spectra and context sensitive languages are closely related, and that their open questions are merely special cases of a family of open questions which relate to the difference between deterministic and nondeterministic time or space bounded Turing machines. Expand

Every Prime has a Succinct Certificate

- Mathematics, Computer Science
- SIAM J. Comput.
- 1975

It remains an open problem whether a prime n can be recognized in only $\log _2^\alpha n$ operations of a Turing machine for any fixed $\alpha $. Expand

Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

- Computer Science
- J. ACM
- 1971

A class of machines called auxiliary pushdown machines is introduced, characterized in terms of time-bounded Turing machines, and corollaries are derived which answer some open questions in the field. Expand

A Comparison of Polynomial Time Reducibilities

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1975

Abstract Various forms of polynomial time reducibility are compared. Among the forms examined are many-one, bounded truth table, truth table and Turing reducibility. The effect of introducing… Expand