Inseparability and Strong Hypotheses for Disjoint NP Pairs

Details Inseparability and Strong Hypotheses for Disjoint NP Pairs Inseparability and Strong Hypotheses for Disjoint NP Pairs

2009-02-16

arxiv.org/abs/0902.2674v4

Computer Science

Computational Complexity

Scientific paper

This paper investigates the existence of inseparable disjoint pairs of NP languages and related strong hypotheses in computational complexity. Our main theorem says that, if NP does not have measure 0 in EXP, then there exist disjoint pairs of NP languages that are P-inseparable, in fact TIME(2^(n^k))-inseparable. We also relate these conditions to strong hypotheses concerning randomness and genericity of disjoint pairs.

Affiliated with

Also associated with

No associations

Rating

Inseparability and Strong Hypotheses for Disjoint NP Pairs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Inseparability and Strong Hypotheses for Disjoint NP Pairs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inseparability and Strong Hypotheses for Disjoint NP Pairs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-463075