Anyone know if this has implications for P=NP, where they’ve found parallels between phase transitions and the “danger zone” of NP-complete problems?
Background: for the NP-complete 3SAT (Boolean satisfiability where the clauses all have up to 3 terms OR’d together), there are ratios of clauses to variables that make instances trivially satisfiable or or trivially unsatisfiable. In between them are the hardest cases, where you run into exponential time blow-up. That transition is analogized to phase transitions in matter.
Background: for the NP-complete 3SAT (Boolean satisfiability where the clauses all have up to 3 terms OR’d together), there are ratios of clauses to variables that make instances trivially satisfiable or or trivially unsatisfiable. In between them are the hardest cases, where you run into exponential time blow-up. That transition is analogized to phase transitions in matter.