Absorbing random walks and the NAE2SAT problem

DOI10.1080/00207161003631893zbMath1213.68337OpenAlexW2089872375MaRDI QIDQ5391499

Xiaofeng Gu, K. Subramani and Vahan Mkrtchyan

Publication date: 6 April 2011

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207161003631893

zbMATH Keywords

verificationerror bounds\(L\)-completeabsorbing random walksNAE2SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Randomized algorithms (68W20)

Related Items (1)

NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Symmetric space-bounded computation
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• An improved exponential-time algorithm for k -SAT
• Undirected ST-connectivity in log-space
• A theory of the learnable
• Symmetric Complementation
• A randomized linear-time algorithm to find minimum spanning trees
• STACS 2004
• Theory and Applications of Satisfiability Testing
• CASCADING RANDOM WALKS
• Theoretical Computer Science

This page was built for publication: Absorbing random walks and the NAE2SAT problem