On the phase transitions of \((k, q)\)-SAT (Q517195): Difference between revisions

The main result of the paper proves an asymptotic zero-one limit of the probability that an instant \((C,Q)\) is satisfiable, i.e., there exists an assignment that does not set any of the \(k\)-tuples of randomly generated Boolean variables in \(C\) to a given bad tuple set of assignments in \(Q\).

0 references

zbMATH Keywords

constraint satisfaction

0 references

phase transition

0 references

second moment method

0 references

reviewed by

Gheorghe Stoica

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s10255-016-0591-8

0 references

cites work

The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

0 references

On the phase transitions of random \(k\)-constraint satisfaction problems

0 references

A general model and thresholds for random constraint satisfaction problems

0 references

A sharp threshold for a random constraint satisfaction problem

0 references

Random \(k\)-SAT: A tight threshold for moderately growing \(k\)

0 references

Q4954175

0 references

Identifiers

zbMATH Open document ID

1359.05134

0 references

DOI

10.1007/s10255-016-0591-8

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:517195

@@ Property / author @@
-Jun Liu
@@ Property / author: Jun Liu / rank @@
-Normal rank
@@ Property / author @@
-Zong Sheng Gao
@@ Property / author: Zong Sheng Gao / rank @@
-Normal rank
@@ Property / author @@
+Jun Liu
@@ Property / author: Jun Liu / rank @@
+Normal rank
@@ Property / author @@
+Zong Sheng Gao
@@ Property / author: Zong Sheng Gao / rank @@
+Normal rank
@@ Property / review text @@
+The main result of the paper proves an asymptotic zero-one limit of the probability that an instant \((C,Q)\) is satisfiable, i.e., there exists an assignment that does not set any of the \(k\)-tuples of randomly generated Boolean variables in \(C\) to a given bad tuple set of assignments in \(Q\).
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+D40
@@ Property / Mathematics Subject Classification ID: 05D40 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6696569
@@ Property / zbMATH DE Number: 6696569 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+constraint satisfaction
@@ Property / zbMATH Keywords: constraint satisfaction / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+phase transition
@@ Property / zbMATH Keywords: phase transition / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+second moment method
@@ Property / zbMATH Keywords: second moment method / rank @@
+Normal rank
@@ Property / reviewed by @@
+Gheorghe Stoica
@@ Property / reviewed by: Gheorghe Stoica / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s10255-016-0591-8
+Normal rank
@@ Property / OpenAlex ID @@
+W2514057803
@@ Property / OpenAlex ID: W2514057803 / rank @@
+Normal rank
@@ Property / cites work @@
+The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
+Normal rank
@@ Property / cites work @@
+On the phase transitions of random \(k\)-constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+A general model and thresholds for random constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+A sharp threshold for a random constraint satisfaction problem
+Normal rank
@@ Property / cites work @@
+Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
+Normal rank
@@ Property / cites work @@
+Q4954175
@@ Property / cites work: Q4954175 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:517195