{"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":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow","scholarly_communication","insufficient_payload"],"consensus_categories":[],"category_scores_codex":[0.001223817,0.0004988511,0.0005480438,0.0007841131,0.001002176,0.001985553,0.002074377,0.0002102805,0.00009856112],"category_scores_gemma":[0.0001647458,0.0004627784,0.0005828827,0.001198628,0.0002769044,0.002366769,0.000917914,0.0005379753,0.000784678],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0002580563,"about_ca_system_score_gemma":0.0002238217,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00002697679,"about_ca_topic_score_gemma":0.00001764626,"domain_scores_codex":[0.9962311,0.00005014262,0.001178517,0.0006453251,0.0007866131,0.001108292],"domain_scores_gemma":[0.9969827,0.0006665615,0.0001450744,0.001307973,0.0004449511,0.0004527483],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.0002651657,0.0007294106,0.00005770104,0.001438422,0.0005013229,0.00001558596,0.01494354,0.0007010068,0.0003387527,0.574672,0.1130349,0.2933021],"study_design_scores_gemma":[0.001262522,0.0005270895,0.0001658091,0.0003715153,0.00003675196,0.0001236199,0.0003097762,0.6075128,0.0008334015,0.06445944,0.3237064,0.0006908276],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.01811058,0.00009663242,0.9695588,0.002190901,0.003172514,0.002257788,0.001234762,0.0009054376,0.002472555],"genre_scores_gemma":[0.1457048,0.00004990895,0.8478696,0.001608219,0.0009386871,0.0006011764,0.0008159287,0.0001278675,0.002283735],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.6068118,"threshold_uncertainty_score":0.9999933,"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."}}