1

In the answer here An Anthology of Complexity Assumptions an interesting assumption is made. The assumption is $p$-measure of $NP$ is not $0$. There are many non-trivial consequences that follow from it that do not follow from a single standard assumption in complexity theory practiced.

  1. I am wondering what has been considered to prove this assumption?

  2. Is there any attempt and do the standard barriers to prove $P\neq NP$ apply here?

  3. Could a single non-deterministic algorithm of some sort prove such an assumption?

Turbo
  • 12,812
  • 1
  • 19
  • 68

0 Answers0