{"id":"W2568886140","doi":"","title":"Completeness for First-order Properties on Sparse Structures with Algorithmic Applications","year":2019,"lang":"en","type":"article","venue":"DSpace@MIT (Massachusetts Institute of Technology)","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":26,"is_retracted":false,"has_abstract":true,"ca_institutions":"Memorial University of Newfoundland","funders":"","keywords":"Tuple; Completeness (order theory); Property (philosophy); Time complexity; Exponential time hypothesis; Data structure; Mathematics; PSPACE; Set (abstract data type); Exponential function; Combinatorics; Class (philosophy); Order (exchange); Discrete mathematics; Computer science; Algorithm; Computational complexity theory","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":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow"],"consensus_categories":[],"category_scores_codex":[0.000135326,0.0003853782,0.0005307139,0.0007261748,0.0003384797,0.00008746337,0.002069998,0.000273211,0.00001172603],"category_scores_gemma":[0.000046496,0.0003059808,0.0001209919,0.001472989,0.0006774259,0.0004515789,0.0003766714,0.0003609943,0.00003222852],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00006812598,"about_ca_system_score_gemma":0.0001549005,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00002545061,"about_ca_topic_score_gemma":0.00009184427,"domain_scores_codex":[0.9978561,0.00001582401,0.0003809669,0.0008280388,0.0003963379,0.0005226881],"domain_scores_gemma":[0.9975429,0.00005314974,0.0002846483,0.001686019,0.0003558322,0.00007747956],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"not_applicable","study_design_scores_codex":[0.000105287,0.00042866,0.002797806,0.0004101357,0.0003330797,0.000011926,0.0003478276,0.004767318,0.002539168,0.9050578,0.0008372422,0.08236374],"study_design_scores_gemma":[0.004673825,0.002076579,0.002570901,0.0005669638,0.0001049276,0.0001296922,0.0002765182,0.06344874,0.02775606,0.08691908,0.8096805,0.001796255],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.07161885,0.0005254595,0.9057476,0.01499867,0.0009152162,0.003780022,0.0001537885,0.001249865,0.001010559],"genre_scores_gemma":[0.6452672,0.00002580342,0.3535177,0.0002255304,0.00006433715,0.0006347229,0.00001817743,0.00003318316,0.0002133024],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.8181387,"threshold_uncertainty_score":0.9999392,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.0212142195922106,"score_gpt":0.2316230426595949,"score_spread":0.2104088230673843,"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."}}