pith. sign in

arxiv: cs/9910003 · v1 · submitted 1999-10-01 · 💻 cs.CC

R_(1-tt)^(SN)(NP) Distinguishes Robust Many-One and Turing Completeness

classification 💻 cs.CC
keywords setscompletemany-onecomplexityproverelativizedrsnnptruth-table
0
0 comments X
read the original abstract

Do complexity classes have many-one complete sets if and only if they have Turing-complete sets? We prove that there is a relativized world in which a relatively natural complexity class-namely a downward closure of NP, \rsnnp - has Turing-complete sets but has no many-one complete sets. In fact, we show that in the same relativized world this class has 2-truth-table complete sets but lacks 1-truth-table complete sets. As part of the groundwork for our result, we prove that \rsnnp has many equivalent forms having to do with ordered and parallel access to $\np$ and $\npinterconp$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.