{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.003908904,0.001111972,0.001527379,0.002000077,0.002241202,0.006112721,0.002787192,0.001966812,0.009627676],"category_scores_gemma":[0.02263419,0.001350465,0.00397765,0.003819547,0.004041844,0.0153415,0.004505504,0.006604528,0.001692917],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003062319,"about_ca_system_score_gemma":0.003987422,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003135548,"about_ca_topic_score_gemma":0.004603138,"domain_scores_codex":[0.9933355,0.001396272,0.0005254713,0.001560959,0.002273347,0.000908464],"domain_scores_gemma":[0.9633101,0.02550902,0.001800185,0.006892142,0.001944801,0.0005438078],"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.0005911087,0.0004847142,0.005404294,0.001084737,0.0001773186,0.0002660443,0.001872873,0.06958362,0.008186041,0.7899352,0.0128485,0.1095656],"study_design_scores_gemma":[0.00005976897,0.00004448796,0.0006569998,0.00003982876,0.00003837523,0.0001583774,0.0001600595,0.08685339,0.004430068,0.9038059,0.00372937,0.00002338393],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1960929,0.0009525346,0.7696678,0.005690772,0.00009936123,0.0003103237,0.003052026,0.004142208,0.01999203],"genre_scores_gemma":[0.6748945,0.0008474988,0.3057446,0.001058841,0.0003964623,0.0004126591,0.006914235,0.001060835,0.0086703],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.009627676,"threshold_uncertainty_score":0.03220779,"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."}}