{"id":"W131197506","doi":"10.1016/j.apal.2005.06.003","title":"What can be efficiently reduced to the Kolmogorov-random strings?","year":2005,"lang":"en","type":"article","venue":"Annals of Pure and Applied Logic","topic":"Computability, Logic, AI Algorithms","field":"Computer Science","cited_by":2,"is_retracted":false,"has_abstract":false,"ca_institutions":"McGill University","funders":"","keywords":"Combinatorics; Time complexity; Mathematics; Decidability; PSPACE; Monotone polygon; Discrete mathematics; Reduction (mathematics); Set (abstract data type); Upper and lower bounds; Binary logarithm; Computational complexity theory; Computer science; Algorithm","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":[],"consensus_categories":[],"category_scores_codex":[0.0007825018,0.0002217671,0.0003277153,0.00009186613,0.0001829858,0.0003103403,0.001085649,0.00008096106,0.00001572394],"category_scores_gemma":[0.00004432715,0.0001494157,0.00009586081,0.0005026557,0.00009984698,0.0002052274,0.0005668299,0.0001724137,0.00001857856],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00001304337,"about_ca_system_score_gemma":0.00004624785,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00001464547,"about_ca_topic_score_gemma":0.00004526222,"domain_scores_codex":[0.9981983,0.00006099041,0.0003407906,0.0005781277,0.0003785866,0.0004432415],"domain_scores_gemma":[0.9986319,0.0002147683,0.000125219,0.0007326844,0.0001184181,0.0001770054],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"bench_or_experimental","study_design_scores_codex":[0.0001067235,0.0005512996,0.00005621243,0.00005257367,0.00007932127,0.00000903371,0.009223608,0.01770158,0.006344687,0.1331095,0.01395906,0.8188064],"study_design_scores_gemma":[0.008874752,0.00351453,0.02238073,0.0003188267,0.0001720705,0.0001870539,0.006984411,0.07995606,0.3530809,0.1926219,0.3272055,0.004703315],"study_design_candidate":"design_other","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.811783,0.002035904,0.05325609,0.127053,0.0006332352,0.001421053,0.00001397738,0.0002457333,0.003557995],"genre_scores_gemma":[0.9857971,0.0001325708,0.005496624,0.008194678,0.0002228654,0.00003680048,0.000002641322,0.000008340101,0.0001084014],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.8141031,"threshold_uncertainty_score":0.6092994,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.0468738684075537,"score_gpt":0.2898112070779778,"score_spread":0.2429373386704241,"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."}}