🐱 Skyspace3.0

Search

SearchSearch

refuting NCP

Feb 16, 20257 min read

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 ” (paraphrased).

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 to be "".

Let be a polynomial-time-sample-able distribution over gate circuits such that .

Then, there should be an efficient weirdness detector (it can depend on ) such that:

  • If , then there exists such that .
  • If , then .

NCP Conjecture 2 Define the weirdness property to be ” is unsatisfiable”.

Let be a polynomial-time-sample-able distribution over clause CNF SAT formulas such that .

Then, there should be an efficient weirdness detector (it can depend on ) such that:

  • If , then there exists such that .
  • If , then .

Related thing that we can easily rule out:

Something impossible Efficient such that

  • , such that .
  • , such that .

Some other things that seem probably true:

probably 1 If (4n clauses) then

BUT it’s like “NP-hard vibes” to find a SAT assignment.

suspicion If then

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 from is at most or something.

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.

Here’s some conjecture:

For a reversible circuit C: {0, 1}^{3n} ⇒ {0, 1}^{3n}, let phi(C) be the property “for all x \in {0, 1}^{2n}, C(0^n ∘ x) does not start with n zeros”. There exists a polynomial-time (maybe even linear-time) verifier V(C, pi) such that: For all C such that phi(C) = 1, there exists pi such that V(C, pi) = 1. For a randomly selected circuit C such that phi(C) = 0, the probability that there exists pi such that V(C, pi) = 1 is <1%.

this is kind of annoying to work with, so I’d love to come up with a cleaner version of it

I guess you can cash this out as having some CNOT gates.

some thoughts:

Planted clique:

magically having a random clique is quite unlikely. but there’s an obvious structure you can point to to prove existence of planted clique.

Suppose I have some function with and . If were Gaussian with this mean and variance, then the probability of having (i.e., standard deviations above the mean) is at most , so it will never happen on any of the input strings.

Thus, if actually is for some , then there must be a structure in which explains why.

next candidate (haven’t thought about whether or not it’s trivially bad yet)

Suppose are independent ‘s. Let be a size set of pairs. Define . Suppose that has standard deviation . Then, any with demands an explanation.

Hi Jacob, Comment about your triangle NCP writeup:

You say

(linear in number of edges time is…) enough time to read in the definition of the graph as a list of edges, but not enough time to count the triangles directly

I think this is kind of questionable. More precisely, there is an algorithm that runs in time (doesn’t need an argument ) with the following properties:

  • If has more than triangles, then .
  • If then .

The algorithm is as follows:

for each vertex v:
   if degree(v) > 10root(n) log n, then just output 1, because this is pretty weird
   else:
       there are at most O(n log^2 n) pairs of neighbors of v
       count how many of these are triangles, add to a global count

I think something interesting is still going on with your pigeon argument though. Here’s my recommendation for what you could say instead.

There is a (randomized) algorithm that is fed an adjacency matrix representation of a graph and an bit proof , such that reads at most bits of and such that satisfies:

  • If has at least triangles, then there is some proof such that .
  • If , then for any , .

proof: expects to be fed a list of triangles that all contain some vertex . checks a couple of random locations in the proof to make sure that they’re actually pointing to legit triangles.

Then, we check to make sure that we don’t actually get fed the same triangle multiple times :P.

I think this does a better job of highlighting how useful the “argument” is. I’m pretty confident you can’t get time for an algorithm without this “argument” .

EDIT: no actually this is kind of silly / not the case that is hard for NCP.

because it has NP vibes not coNP vibes.

Suppose that and we’re guaranteed that either or . There is a Verifier that, given a length proof, will read bits of the proof and:

  • An honest Prover can write down a proof of that the Verifier will always accept.
  • An evil Prover with cannot write down any proof that has probability more than of tricking the Verifier into accepting.

The Prover writes down the elements of in sorted order. The Verifier looks at a random sequence of the elements as follows:

  • First, look at number .
  • Then, randomly choose one side or to recurse on.
  • Then you’ll ask something like . etc.Claim At the end you’ll just check that these elements are all in and are in the correct order.

Clearly the honest Prover can write down a proof that we’ll be happy about.

**Claim**: the probability that an evil Prover wins is very low.

Proof: Let . We have . Let be either the things larger than or less than randomly. Similarly define based on . Then, .

Basically, going deep enough we can get . At which point we must see repeated elements — if we haven’t seen a contradiction earlier.

Had some problem like this:

is a graph with edges and . Let . Turns out

Question: Can we distinguish between

with one sided error

in non-deterministic time ?

I’ve kind of decided that this is maybe not such an interesting problem / isn’t going to be useful in refining or refuting NCP, but here it is anyways.

Graph View

Backlinks

  • No backlinks found