{"id":"W2062671967","doi":"10.1016/j.jcss.2003.07.011","title":"A sharp threshold in proof complexity yields lower bounds for satisfiability search","year":2003,"lang":"en","type":"article","venue":"Journal of Computer and System Sciences","topic":"Constraint Satisfaction and Optimization","field":"Computer Science","cited_by":61,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Toronto","funders":"","keywords":"Satisfiability; Mathematics; Combinatorics; Resolution (logic); Range (aeronautics); Conjunctive normal form; Discrete mathematics; Exponential function; Boolean satisfiability problem; Upper and lower bounds; Exponential time hypothesis; Time complexity; Computer science","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.02625149,0.00490571,0.006115537,0.007220441,0.003231021,0.01461067,0.01040583,0.00904359,0.01858016],"category_scores_gemma":[0.2205057,0.005166959,0.006070323,0.007180035,0.0106113,0.04105743,0.01352857,0.03105208,0.005245871],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.009107842,"about_ca_system_score_gemma":0.007143813,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002024217,"about_ca_topic_score_gemma":0.002760963,"domain_scores_codex":[0.964872,0.009988924,0.001730768,0.005672005,0.01157643,0.006159866],"domain_scores_gemma":[0.6076341,0.3440857,0.005884812,0.02936894,0.007326073,0.005700343],"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.002093798,0.0007890539,0.003727982,0.001905525,0.0003469287,0.0003614933,0.0009550284,0.09868736,0.0150813,0.6882346,0.02612913,0.1616879],"study_design_scores_gemma":[0.0001100511,0.00022928,0.0006906259,0.0003653189,0.0002010628,0.000332812,0.0001183452,0.3218755,0.008001424,0.6624849,0.005488024,0.0001026822],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.02656274,0.01002049,0.9141059,0.01232988,0.000700959,0.0002842174,0.000731241,0.003295328,0.03196933],"genre_scores_gemma":[0.5587479,0.008991348,0.3966438,0.00629099,0.0030227,0.001146468,0.001357428,0.004838461,0.01896101],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.02625149,"threshold_uncertainty_score":0.1388327,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.05440909133257375,"score_gpt":0.293218237044864,"score_spread":0.2388091457122902,"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."}}