{"id":"W2109734774","doi":"10.1109/focs.2008.70","title":"A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems","year":2008,"lang":"en","type":"article","venue":"","topic":"Constraint Satisfaction and Optimization","field":"Computer Science","cited_by":4,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"","keywords":"Constraint satisfaction problem; Mathematics; Constraint (computer-aided design); Random variable; Closure (psychology); Constraint satisfaction; Discrete mathematics; Constant (computer programming); Complexity of constraint satisfaction; Set (abstract data type); Resolution (logic); Computational complexity theory; Domain (mathematical analysis); Constraint satisfaction dual problem; Constraint graph; Combinatorics; Local consistency; Computer science; Algorithm; Statistics; Artificial intelligence","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.0003774385,0.00009026478,0.0001346794,0.00006148808,0.0003110854,0.00002969839,0.0001883171,0.00004266245,0.00009384487],"category_scores_gemma":[0.00007419351,0.00006050961,0.0000933706,0.0002083232,0.0004549803,0.0002502569,0.00003687504,0.00006971703,0.000004287089],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00003152652,"about_ca_system_score_gemma":0.00008355894,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0001474824,"about_ca_topic_score_gemma":0.000158485,"domain_scores_codex":[0.9991351,0.00006728154,0.0002788756,0.0001897935,0.000187306,0.0001416634],"domain_scores_gemma":[0.9990309,0.0003383533,0.0001456147,0.0002807898,0.0001663166,0.00003797037],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.00007929635,0.00004385987,0.004393736,0.00002368617,0.00005104516,6.104169e-7,0.001116,0.007993683,0.00106974,0.9131402,0.001042527,0.07104559],"study_design_scores_gemma":[0.003094133,0.0001027742,0.08579185,0.00001991028,0.00001667639,0.000112713,0.0001252292,0.8858962,0.001449414,0.02158572,0.001621134,0.0001842599],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.003653777,0.00003381953,0.9910308,0.00145438,0.0002097167,0.0008377605,0.000006737265,0.0001215328,0.002651453],"genre_scores_gemma":[0.9311301,0.00005562805,0.06852021,0.0001211079,0.00002231884,0.0000580848,0.00000369484,0.000003925704,0.00008491374],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.9274763,"threshold_uncertainty_score":0.246751,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.04980244377209592,"score_gpt":0.2537608392377873,"score_spread":0.2039583954656913,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}