Relative to a random oracle, NP is not small

Παρόμοια τεκμήρια

• Lower bounds for Union-Split-FIND related problems on rendom access machines
  ανά: Miltersen Bro, Peter
• On the cell probe complexity of polynomial evaluation
  ανά: Miltersen Bro, Peter
• Consistency of natural relations on sets
  ανά: Koizumi, H., κ.ά.
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
  ανά: Dancik, V., κ.ά.
• PI mass production and an optimal circuit for the nechiporuk slice
  ανά: Hiltgen, Alain P., κ.ά.