Skip to main content
Add tags
Link
Hermann Gruber
  • 6.8k
  • 1
  • 36
  • 62
Tweeted twitter.com/StackCSTheory/status/745331027531468801
Source Link
Springberg
  • 696
  • 3
  • 14

P/Poly vs Uniform Complexity Classes

It is not known whether NEXP is contained in P/poly. Indeed proving that NEXP is not in P/poly would have some applications in derandomization.

  1. What is the smallest uniform class C for which one can prove that C is not contained in P/poly?

  2. Would showing that co-NEXP is not contained in P/poly have some other complexity theoretic consequences as in the case NEXP vs P/poly?

Note: I'm aware that $SP_2$ is known not to be contained in $Size[n^k]$ for each fixed constant $k$ (This was also shown for MA with 1 bit of advice). But in this question I'm not interested in results for fixed $k$. I'm really interested in classes which are different from P/Poly, even if these classes are very large.