{"id":"W3000821546","doi":"10.5555/1704843.1705075","title":"Typical case complexity of Satisfiability Algorithms and the threshold phenomenon","year":2005,"lang":"en","type":"article","venue":"Discrete Applied Mathematics","topic":"Constraint Satisfaction and Optimization","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"","funders":"","keywords":"Satisfiability; Mathematics; Algorithm; Phenomenon; Computational complexity theory; Boolean satisfiability problem; Subject (documents); Theoretical computer science; Computer science","routes":{"ca_aff":false,"ca_fund":false,"ca_venue":false,"about_ca":true,"invisible_to_affiliation_only":true},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.00700694,0.0007829962,0.002216063,0.002807904,0.001637784,0.008595724,0.003464146,0.002611373,0.009760234],"category_scores_gemma":[0.07611279,0.001015716,0.002557654,0.004520406,0.005405513,0.01738708,0.003779783,0.005777082,0.0008508818],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003340303,"about_ca_system_score_gemma":0.001536707,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001081067,"about_ca_topic_score_gemma":0.0008265411,"domain_scores_codex":[0.9844114,0.004386207,0.001142399,0.002682585,0.005854408,0.001523023],"domain_scores_gemma":[0.8887868,0.09391297,0.003736427,0.00757627,0.003925108,0.002062466],"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.0001377024,0.00008879906,0.0021972,0.0003835005,0.0001005665,0.0002243934,0.0003254814,0.02408399,0.00100721,0.9446197,0.00470819,0.02212332],"study_design_scores_gemma":[0.00001561921,0.00001585379,0.0003518026,0.00002342843,0.00002224954,0.0002430596,0.00005239935,0.04971149,0.0004576091,0.9471376,0.001952782,0.00001612156],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1365676,0.005562385,0.7985722,0.008945878,0.0002891325,0.0002075708,0.0008929389,0.001026687,0.04793564],"genre_scores_gemma":[0.8582605,0.003660781,0.1283845,0.0008567136,0.001013945,0.0003790674,0.0008990311,0.0003744904,0.006171032],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.009760234,"threshold_uncertainty_score":0.03705668,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02678851015357779,"score_gpt":0.2563801699547778,"score_spread":0.2295916598012,"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."}}