### random k-sat

Posted:

**Wed Aug 29, 2018 6:30 pm UTC**hi,

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?

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?