Phase Transition in Probabilistic Satisfiability

• Grant number: 13/22445-4
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: December 01, 2013
• End date: July 31, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science
• Principal Investigator: Fabio Gagliardi Cozman
• Grantee: Fábio Tosetto Reale
• Host Institution: Escola Politécnica (EP). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

The objective of this work is to investigate phase transition phenomena for the probabilistic satisfiability problem (PSAT), using a new algorithm, recently developed by the advisor. The study will focus on problems with only two literals per clause (2-PSAT).This focus is due to the fact that phase transition is a well known phenomenon in (non-probabilistic) satisfiability problems in conjunctive normal form, with two literals (2-SAT).