Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let Tk（V） denote the set of all 2^kn^k possible k-tuples on V. Randomly generate a set C of k-tuples by includ...Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let Tk（V） denote the set of all 2^kn^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in Tk（V） independently with probability p, and let Q be a given set of q ＂bad＂ tuple assignments. An instance I = （C, Q） is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tupie assignment in Q. Suppose that θ, q 〉 0 are fixed and ε=ε（n） 〉 0 be such in 2 that ε Inn/ In Inn → ∞. Let k ≥ （1 ＋ θ） log2 n and let p0 = ln2/qn^k-1. We prove thatlim∞ P[I issatisfiable] ={1,p≤（1-ε）p0, 0,p≥（1＋ε）p0.展开更多
基金supported by NSFC(Grant No.11371225)the fund of the State Key Lab of Software Development Environment(Grant No.SKLSDE-2015ZX-05)
文摘Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let Tk（V） denote the set of all 2^kn^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in Tk（V） independently with probability p, and let Q be a given set of q ＂bad＂ tuple assignments. An instance I = （C, Q） is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tupie assignment in Q. Suppose that θ, q 〉 0 are fixed and ε=ε（n） 〉 0 be such in 2 that ε Inn/ In Inn → ∞. Let k ≥ （1 ＋ θ） log2 n and let p0 = ln2/qn^k-1. We prove thatlim∞ P[I issatisfiable] ={1,p≤（1-ε）p0, 0,p≥（1＋ε）p0.
