{"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":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.00609504,0.0001132803,0.0002559967,0.0001162539,0.001192517,0.000811191,0.00113564,0.00002666836,3.416655e-7],"category_scores_gemma":[0.00004613228,0.00004986495,0.0001045361,0.0006815149,0.0007745577,0.0004444603,0.0003988388,0.000150129,0.000002462186],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00001333363,"about_ca_system_score_gemma":0.00007300213,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00001795454,"about_ca_topic_score_gemma":0.000009032452,"domain_scores_codex":[0.9982402,0.0003134,0.0004407329,0.0002094334,0.000548207,0.0002479953],"domain_scores_gemma":[0.997421,0.001825359,0.0002962695,0.000246446,0.0001204921,0.00009049098],"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.00003125995,0.00002141534,0.003281841,0.0001130091,0.00006475645,0.00002436047,0.004272838,0.0006377388,0.00001119808,0.6631645,0.001941071,0.326436],"study_design_scores_gemma":[0.0008464843,0.0003567013,0.01682512,0.0002011964,0.00001656008,0.0007703126,0.001060421,0.8880677,0.00003995236,0.08843999,0.00320092,0.0001746459],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.34328,0.00397986,0.6144635,0.03204465,0.002977181,0.0007368732,0.000003583634,0.0001963976,0.002317928],"genre_scores_gemma":[0.9504634,0.0002047495,0.04889229,0.00009901013,0.0002847334,0.00000310661,2.388677e-8,0.000003119723,0.0000496095],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.88743,"threshold_uncertainty_score":0.9172,"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."}}