Fractal structure on k-SAT

DOI10.1142/S0218348X11005269zbMATH Open1223.68042MaRDI QIDQ3087540FDOQ3087540

Authors: Qin Wang, Lifeng Xi 

Publication date: 16 August 2011

Published in: Fractals (Search for Journal in Brave)

Recommendations

• SELF-SIMILARITY OF SATISFIABLE BOOLEAN EXPRESSIONS DECIPHERED IN TERMS OF GRAPH DIRECTED ITERATED FUNCTION SYSTEMS
• The \(k\)-SATISFIABILITY problem remains NP-complete for dense families
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• The fractal dimension of SAT formulas
• scientific article; zbMATH DE number 1189117

zbMATH Keywords

Hausdorff dimensionMoran set\(k\)-satisfiability problem (\(k\)-SAT)

Mathematics Subject Classification ID

Fractals (28A80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• SELF-SIMILARITY OF SATISFIABLE BOOLEAN EXPRESSIONS DECIPHERED IN TERMS OF GRAPH DIRECTED ITERATED FUNCTION SYSTEMS

Cited In (7)

• Asymptotic formula on average path length of a special network based on Sierpinski carpet
• Two-point resistances in sailboat fractal networks
• Eigentime identities of flower networks with multiple branches
• Title not available (Why is that?)
• SELF-SIMILARITY OF SATISFIABLE BOOLEAN EXPRESSIONS DECIPHERED IN TERMS OF GRAPH DIRECTED ITERATED FUNCTION SYSTEMS
• Scale-free and small-world properties of a special hierarchical network
• Eigentime identities of fractal sailboat networks

This page was built for publication: Fractal structure on \(k\)-SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3087540)