Collapsing and separating completeness notions under average-case and worst-case hypotheses
X Gu, JM Hitchcock, A Pavan - Theory of Computing Systems, 2012 - Springer
X Gu, JM Hitchcock, A Pavan
Theory of Computing Systems, 2012•SpringerThis paper presents the following results on sets that are complete for NP.(i) If there is a
problem in NP that requires 2^n^Ω(1) time at almost all lengths, then every many-one NP-
complete set is complete under length-increasing reductions that are computed by
polynomial-size circuits.(ii) If there is a problem in co-NP that cannot be solved by
polynomial-size nondeterministic circuits, then every many-one NP-complete set is complete
under length-increasing reductions that are computed by polynomial-size circuits.(iii) If there …
problem in NP that requires 2^n^Ω(1) time at almost all lengths, then every many-one NP-
complete set is complete under length-increasing reductions that are computed by
polynomial-size circuits.(ii) If there is a problem in co-NP that cannot be solved by
polynomial-size nondeterministic circuits, then every many-one NP-complete set is complete
under length-increasing reductions that are computed by polynomial-size circuits.(iii) If there …
Abstract
This paper presents the following results on sets that are complete for NP.
- (i) If there is a problem in NP that requires time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.
- (ii) If there is a problem in co-NP that cannot be solved by polynomial-size nondeterministic circuits, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits.
- (iii) If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in NP∩co-NP, then there is a Turing complete language for NP that is not many-one complete.
Springer