{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001825587,0.0008018348,0.002051078,0.0009366575,0.002612763,0.005739216,0.002244055,0.003075045,0.02431296],"category_scores_gemma":[0.02104072,0.0007496533,0.002072011,0.001256182,0.004172837,0.01485883,0.003843332,0.004727285,0.005824235],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.001299445,"about_ca_system_score_gemma":0.00274793,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00140165,"about_ca_topic_score_gemma":0.001561204,"domain_scores_codex":[0.9967912,0.001086168,0.0001637707,0.0006123285,0.0006793282,0.0006672634],"domain_scores_gemma":[0.9908018,0.005312159,0.0002726619,0.002655882,0.0005941086,0.0003635036],"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.0001313502,0.00009029101,0.0001664752,0.0001383111,0.00003119053,0.00005281108,0.0001603942,0.004106557,0.0006105336,0.9683959,0.01103732,0.01507886],"study_design_scores_gemma":[0.0000182579,0.000008695797,0.00004547538,0.0000159608,0.00001227102,0.00002222461,0.00004194117,0.005663271,0.0003671032,0.9904096,0.003385857,0.000009359544],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2488906,0.003536722,0.4343458,0.04707644,0.003115794,0.0003144298,0.002339186,0.004274467,0.2561066],"genre_scores_gemma":[0.8602511,0.001599237,0.08556551,0.003941559,0.001531683,0.0003447471,0.001948456,0.001453527,0.04336412],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.02431296,"threshold_uncertainty_score":0.08133489,"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."}}