{"id":"W1997649256","doi":"10.1145/1120582.1120584","title":"A dichotomy theorem for constraint satisfaction problems on a 3-element set","year":2006,"lang":"en","type":"article","venue":"Journal of the ACM","topic":"Constraint Satisfaction and Optimization","field":"Computer Science","cited_by":372,"is_retracted":false,"has_abstract":true,"ca_institutions":"Simon Fraser University","funders":"","keywords":"Constraint satisfaction problem; Constraint satisfaction; Constraint (computer-aided design); Element (criminal law); Set (abstract data type); Mathematics; Domain (mathematical analysis); Class (philosophy); Local consistency; Time complexity; Constraint satisfaction dual problem; Maximal element; Mathematical optimization; Algebraic number; Computer science; Discrete mathematics; 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.0039638,0.001062075,0.001726628,0.002060372,0.002463088,0.006370883,0.002356482,0.002341533,0.01302575],"category_scores_gemma":[0.01506346,0.0007615853,0.003427427,0.002884744,0.006054336,0.01275586,0.004924457,0.01078844,0.001793865],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0035235,"about_ca_system_score_gemma":0.001881288,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001739468,"about_ca_topic_score_gemma":0.001254004,"domain_scores_codex":[0.9946779,0.001097672,0.0002824451,0.001122368,0.002154012,0.0006655491],"domain_scores_gemma":[0.9804007,0.01699543,0.0006746221,0.0008134098,0.0007067856,0.0004091511],"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.000139453,0.0001150158,0.0005150461,0.0003075032,0.00005596739,0.0001197092,0.0003747119,0.01475275,0.001345264,0.9472016,0.007054168,0.02801875],"study_design_scores_gemma":[0.00004267443,0.00004022825,0.0002859077,0.00005424004,0.00001803614,0.0001011036,0.00006563434,0.04952151,0.0008195988,0.9435154,0.005518297,0.00001727925],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.05274674,0.001830075,0.8615219,0.01060711,0.0002129511,0.0003497005,0.001170287,0.0005590213,0.07100215],"genre_scores_gemma":[0.6085934,0.004021517,0.3576058,0.004983801,0.001430844,0.002032176,0.003176625,0.0004230706,0.01773291],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01302575,"threshold_uncertainty_score":0.04357553,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01866132233556832,"score_gpt":0.2543906495361,"score_spread":0.2357293272005317,"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."}}