Paper Info
Title
Lower Bounds by Recursion Theoretic Arguments (Extended Abstract)
Abstract
Using methods and notions stemming from recursion theory, new lower bounds on the "distance" between certain intractable sets (like NP-complete or EXPTIME-complete sets) and the sets in P are obtained. Here, the distance of two sets A and B is a function on natural numbers that, for each n, gives the number of strings of size n on which A and B differ. Yesha [6] has shown that each NP-complete set has a distance of at least O(log log n) from each set in P, assuming P ≠ NP. Similarly, whithout an additional assumption, each EXPTIME-complete set has a distance of at least O(log log n) from each set in P.
Year
DOI
Venue
1986
10.1007/3-540-16761-7_86
ICALP
Keywords
Field
DocType
recursion theoretic arguments,extended abstract,lower bounds,recursion theory,lower bound
Discrete mathematics,Combinatorics,Double recursion,Recursion,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-16761-7
0
0.34
References 
Authors
6
1
Name
Order
Citations
PageRank
Uwe Schöning1998105.69