{"id":"W6929079456","doi":"10.4230/lipics.approx/random.2024.51","title":"Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity","year":2024,"lang":"en","type":"article","venue":"DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":1,"is_retracted":false,"has_abstract":true,"ca_institutions":"Simon Fraser University","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Kolmogorov complexity; Randomized algorithm; Constant (computer programming); Reduction (mathematics); Time complexity; Computational complexity theory; Class (philosophy); Running time","routes":{"ca_aff":true,"ca_fund":true,"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.009136315,0.0009563541,0.001763608,0.0009031567,0.002486654,0.004343642,0.004266085,0.002713376,0.00751722],"category_scores_gemma":[0.05986736,0.00119659,0.004000208,0.000927161,0.007877676,0.01232699,0.007895005,0.01374832,0.00091677],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003837841,"about_ca_system_score_gemma":0.003412561,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001933296,"about_ca_topic_score_gemma":0.001830324,"domain_scores_codex":[0.976954,0.008319974,0.0009070592,0.004607961,0.006482365,0.00272863],"domain_scores_gemma":[0.8999324,0.07932898,0.002900705,0.01398797,0.002420186,0.001429666],"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.0008844421,0.0003954652,0.003119438,0.0003489397,0.0001676956,0.0003458677,0.0005855428,0.07040807,0.006905611,0.8919663,0.007843668,0.01702902],"study_design_scores_gemma":[0.0002929767,0.0002232409,0.002185151,0.00006938023,0.0001112744,0.0002561311,0.0002540756,0.1651316,0.008754905,0.8167284,0.005910224,0.00008255032],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2591823,0.001574124,0.6233323,0.03054428,0.0008064607,0.0005700187,0.001451383,0.003935889,0.07860328],"genre_scores_gemma":[0.9225101,0.0007037428,0.06067731,0.004494491,0.0007943668,0.0007440215,0.0008799609,0.0009519675,0.008244081],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.009136315,"threshold_uncertainty_score":0.04831803,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02830620384657163,"score_gpt":0.2812607922792531,"score_spread":0.2529545884326815,"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."}}