random k-sat

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 1
Joined: Wed Aug 29, 2018 6:09 pm UTC

random k-sat

Postby omygod » Wed Aug 29, 2018 6:30 pm UTC


I know that if I have a random k-sat formula on n variables, the probability it satisfiable depend on the number of constraints in the formula.
I want to prove that if the formula has n/1000 constraints than it will be satisfiable with probability going to 1 when n going to inf. I tried to do that by making a bi-partite graph that links constraint to variables and proves it with hall's marriage theorem but it didn't work out.
I also want to prove that formula with (2^k)*n constraints is unsatisfiable with probability going to 1 when n going to inf.

any suggestions?

Posts: 217
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: random k-sat

Postby DavidSh » Fri Aug 31, 2018 10:24 pm UTC

Have you done Monte-Carlo experiments to indicate whether either of your desired results is likely to be true?

Also, if you allow for k=1, you can more easily analyze that case.

For k=1, the results on the Birthday Problem suggest that if you have on the order of sqrt(n) terms, the chance of having two terms that repeat a variable is bounded above 0. So the chance of having "x" and "not x" both as terms for some variable x is bounded above zero. I would conclude that having n/1000 terms (asymptotically much larger than sqrt(n) terms) does not "make the formula satisfiable with probability converging to 1".

But k=1 is a special case, and this simple analysis doesn't easily extend to k>1.

For k=2, it looks like random graph theory says that the probability of satisfiability, for m = c * n, for any 0 < c < 1/2, converges to a value depending on c that is strictly between 0 and 1. (Basically, if you make a graph where the variables are the nodes, and the terms are the edges, the probability of at least one cycle converges like this, as does the probability of at least one cycle of length H for about any H. Any cycle has a probability of causing a contradiction depending on its length.) Your first case where m = n/1000 falls here.

Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 15 guests