{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.01236746,0.001608933,0.003008212,0.0026493,0.002564304,0.007036037,0.004708983,0.003304415,0.01078601],"category_scores_gemma":[0.0840169,0.001096112,0.002776613,0.002862101,0.006847473,0.01999717,0.006400936,0.01075676,0.001416907],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005062469,"about_ca_system_score_gemma":0.00238004,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001128613,"about_ca_topic_score_gemma":0.0006674369,"domain_scores_codex":[0.9894906,0.003553557,0.0004507517,0.002000579,0.003121288,0.001383303],"domain_scores_gemma":[0.8805782,0.1063416,0.003228092,0.006113458,0.001980776,0.001757876],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0003864398,0.0002216557,0.001461081,0.0003551962,0.000128304,0.0002301518,0.0003809858,0.05576056,0.002396154,0.9046036,0.007462662,0.02661338],"study_design_scores_gemma":[0.00008934894,0.00006350125,0.0005236057,0.00005159721,0.0000311129,0.0001649623,0.00005850802,0.2289848,0.0009430324,0.7673431,0.001709808,0.00003661617],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.105683,0.002456732,0.8468935,0.0138829,0.0002262584,0.0002740968,0.001040237,0.0008889916,0.02865427],"genre_scores_gemma":[0.8518386,0.002582701,0.1279757,0.003416127,0.001347434,0.001555341,0.00168903,0.0006548401,0.008940328],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01236746,"threshold_uncertainty_score":0.06540614,"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."}}