{"id":"W6910201977","doi":"10.4230/lipics.ccc.2024.29","title":"Exact Search-To-Decision Reductions for 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":3,"is_retracted":false,"has_abstract":true,"ca_institutions":"Simon Fraser University","funders":"University of Warwick; UK Research and Innovation","keywords":"Reduction (mathematics); Bounded function; String (physics); Measure (data warehouse); Kolmogorov complexity; Upper and lower bounds","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.004618606,0.001514687,0.001572003,0.001655121,0.001456898,0.003857465,0.003662785,0.001421138,0.006955744],"category_scores_gemma":[0.03314313,0.0007793182,0.004196796,0.001556852,0.004434024,0.009406886,0.005438886,0.01014346,0.001446746],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005568657,"about_ca_system_score_gemma":0.005200077,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002296956,"about_ca_topic_score_gemma":0.003708636,"domain_scores_codex":[0.9862694,0.002225198,0.0006636133,0.003001976,0.006265182,0.001574621],"domain_scores_gemma":[0.958966,0.03101067,0.001310267,0.006095325,0.00195456,0.000663017],"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.0004681516,0.0003767232,0.0009258122,0.0004382801,0.0001103286,0.0001633747,0.0003901511,0.1672636,0.009659432,0.7430705,0.00794553,0.06918819],"study_design_scores_gemma":[0.0000788048,0.0000892474,0.0003079745,0.00003909802,0.00007043177,0.00007659987,0.00004304837,0.3670562,0.007618033,0.6209617,0.003616375,0.00004244285],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.03366086,0.0005848559,0.9457294,0.001989073,0.0001647905,0.0002492879,0.0004947327,0.002287109,0.01483987],"genre_scores_gemma":[0.5821951,0.0007664484,0.3990467,0.001580999,0.0006207717,0.001051829,0.001372146,0.001418663,0.01194732],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.006955744,"threshold_uncertainty_score":0.0404036,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.0385608933092483,"score_gpt":0.3119794596525081,"score_spread":0.2734185663432598,"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."}}