{"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":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow"],"consensus_categories":[],"category_scores_codex":[0.001201595,0.0004155861,0.001063604,0.0005298608,0.0003836887,0.0008611758,0.001649121,0.0001635904,0.0001660346],"category_scores_gemma":[0.0002539741,0.0003586535,0.0006770326,0.0008909397,0.0009669875,0.001529074,0.0006085081,0.0003851474,0.0003972957],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0001107748,"about_ca_system_score_gemma":0.0002131668,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0002185682,"about_ca_topic_score_gemma":0.00002985791,"domain_scores_codex":[0.9965396,0.0001387484,0.001606391,0.000450349,0.0006514898,0.0006134455],"domain_scores_gemma":[0.9971541,0.0009294173,0.0003267143,0.0009837789,0.0003387089,0.0002673508],"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.003098345,0.0006274388,0.0001487417,0.001027974,0.001871928,0.00002243185,0.03600877,0.0002938843,0.002304501,0.9001415,0.02348574,0.03096878],"study_design_scores_gemma":[0.03627253,0.000468739,0.0001768787,0.001250392,0.0002879261,0.0001694252,0.001244881,0.4015275,0.01425557,0.4603828,0.08236941,0.001593949],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1145089,0.0004436868,0.8634018,0.00435127,0.004461538,0.003010039,0.002693662,0.0009037001,0.006225333],"genre_scores_gemma":[0.5642308,0.00007514454,0.4323677,0.001135337,0.0003742426,0.0003301969,0.0007185279,0.00005247396,0.0007156037],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.4497219,"threshold_uncertainty_score":0.9998866,"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."}}