{"id":"W4385005490","doi":"10.1145/3632872","title":"Strong Invariants Are Hard: On the Hardness of Strongest Polynomial Invariants for (Probabilistic) Programs","year":2024,"lang":"en","type":"article","venue":"Proceedings of the ACM on Programming Languages","topic":"Formal Methods in Verification","field":"Computer Science","cited_by":6,"is_retracted":false,"has_abstract":true,"ca_institutions":"","funders":"European Research Council; Technische Universität Wien; Vienna Science and Technology Fund; McGill University","keywords":"Invariant (physics); Probabilistic logic; Mathematics; Polynomial; Decidability; Bracket polynomial; Reachability; Discrete mathematics; Matrix polynomial; Combinatorics; Square-free polynomial; Mathematical analysis","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.001725815,0.0002577121,0.0002988768,0.0001294209,0.0001882211,0.0004699035,0.004060489,0.000114621,0.000003722863],"category_scores_gemma":[0.004308791,0.0001521303,0.0001874655,0.0006534751,0.000229825,0.0004352152,0.0007815893,0.0003209168,0.000004702996],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00007858992,"about_ca_system_score_gemma":0.00007699365,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00003001139,"about_ca_topic_score_gemma":0.000003585326,"domain_scores_codex":[0.9979942,0.00004209998,0.0004484162,0.0005461581,0.0005455394,0.0004236015],"domain_scores_gemma":[0.9978996,0.0003333657,0.00046164,0.0009623649,0.0002818644,0.00006116886],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"bench_or_experimental","study_design_scores_codex":[0.0001628115,0.0004310414,0.001942421,0.001334292,0.0001672423,0.000001729852,0.003391155,0.00001909927,0.006144425,0.5765191,0.002402911,0.4074837],"study_design_scores_gemma":[0.003587988,0.007636369,0.056676,0.0138383,0.0007302297,0.0001127714,0.01852362,0.0515633,0.757559,0.05213481,0.03472137,0.00291626],"study_design_candidate":"bench_or_experimental","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.9588588,0.0008003613,0.01300169,0.01342631,0.003421181,0.007381241,0.0001013902,0.0009492973,0.002059763],"genre_scores_gemma":[0.8111163,0.000004396438,0.1880538,0.00006478887,0.0001554189,0.0003826671,0.000002499064,0.00003313256,0.0001870002],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.7514145,"threshold_uncertainty_score":0.7545466,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.06247433803599339,"score_gpt":0.307724305620952,"score_spread":0.2452499675849587,"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."}}