ARC is currently pretty excited about something called “no coincidence principle”.
My complexity theory expert friend N says that “NCP basically sounds like you’re trying to show
I’m fairly sympathetic to this view.
My view is that NCP should be true for many “squishy systems” (roughly “compressible”) for “dumb reasons” but shouldn’t be true in general.
Let’s gather some evidence.
EDIT — these “don’t count”
NCP Conjecture 1
Define the weirdness property
Let
Then, there should be an efficient weirdness detector
- If
, then there exists such that . - If
, then .
NCP Conjecture 2
Define the weirdness property
Let
Then, there should be an efficient weirdness detector
- If
, then there exists such that . - If
, then .
Related thing that we can easily rule out:
Something impossible
Efficient
, such that . , such that .
Some other things that seem probably true:
probably 1
If
BUT it’s like “NP-hard vibes” to find a SAT assignment.
suspicion
If
BUT it’s like “coNP-hard vibes” to prove this.
in fact,… it is known that it usually requires exponentially long “refutation” proofs.
of course this doesn’t rule out the existence of some other shorter type of proof but it doesn’t seem good.
ah, according to Jacob — my assumptions here are not really kosher.
what you’re supposed to do is give a “heuristic argument” for why the probability is really low, but then it’s not actually supposed to be that low (or else you can union bound). and then you’re supposed to do it.
like if we’re forall quantifying over things
yeah yeah
hmm.
ok in Jacob’s example the heuristic that he used was something like
Pr deviating by more than
So maybe I need some setup where I use this heuristic to estimate the number of something, but then this heuristic didn’t apply super well?
yeah atm I don’t get why NCP isn’t just true by union bound. sigh.
lets try something else.