{"id":"W2760351616","doi":"10.1016/j.jcss.2023.03.001","title":"The 2CNF Boolean formula satisfiability problem and the linear space hypothesis","year":2023,"lang":"en","type":"article","venue":"Journal of Computer and System Sciences","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":10,"is_retracted":false,"has_abstract":false,"ca_institutions":"","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Parameterized complexity; Mathematics; Nondeterministic algorithm; Discrete mathematics; Maximum satisfiability problem; True quantified Boolean formula; Linear space; Boolean satisfiability problem; Time complexity; Satisfiability; Space (punctuation); Polynomial; Boolean domain; Combinatorics; NP; Boolean function; Algebra over a field; Algorithm; Computer science; Pure mathematics; Two-element Boolean algebra; Turing machine; Computation","routes":{"ca_aff":false,"ca_fund":true,"ca_venue":false,"about_ca":false,"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.002857141,0.0006209755,0.001480379,0.00191766,0.001732259,0.004253521,0.002871655,0.003405133,0.01569578],"category_scores_gemma":[0.02898236,0.0007738266,0.00186017,0.002848424,0.004249814,0.01421368,0.002418668,0.004900195,0.0008140416],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002758615,"about_ca_system_score_gemma":0.002531107,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.007519707,"about_ca_topic_score_gemma":0.005073801,"domain_scores_codex":[0.9964784,0.00125954,0.0001494784,0.0007607487,0.000749139,0.0006027699],"domain_scores_gemma":[0.9569326,0.03815278,0.001605314,0.001455506,0.001144757,0.0007090889],"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.0004264009,0.0002860128,0.00265578,0.0004985263,0.0001013113,0.000366201,0.0004422964,0.04750744,0.000837084,0.8804126,0.02051162,0.04595476],"study_design_scores_gemma":[0.00006737347,0.00002203896,0.0004522677,0.00003455477,0.00001777156,0.0001432496,0.0001476244,0.07835668,0.0004254091,0.9182221,0.002087302,0.00002362651],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.3646302,0.0042694,0.4989631,0.05306876,0.0007171161,0.0002584731,0.003999745,0.0009480025,0.07314514],"genre_scores_gemma":[0.9147422,0.001554004,0.06590623,0.002163566,0.001432164,0.0002199359,0.002235328,0.0001819203,0.01156458],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01569578,"threshold_uncertainty_score":0.05250764,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02440004977470865,"score_gpt":0.2432979119986418,"score_spread":0.2188978622239332,"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."}}