{"id":"W2132910148","doi":"10.1109/sct.1989.41812","title":"On the theory of average case complexity","year":2003,"lang":"en","type":"article","venue":"","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":36,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"","keywords":"Complexity class; Nondeterministic algorithm; Time complexity; NP; Mathematics; Computational complexity theory; Structural complexity theory; Equivalence (formal languages); PH; Average-case complexity; PSPACE; Exponential function; Polynomial hierarchy; Hierarchy; Discrete mathematics; Descriptive complexity theory; Time hierarchy theorem; Counting problem; Context (archaeology); Quantum complexity theory; Algorithm; Turing machine; Computation","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.0006827747,0.00007751463,0.0000906354,0.00004093516,0.0001733313,0.00003787109,0.0004935307,0.00001975503,0.0005374418],"category_scores_gemma":[0.0001037724,0.00004648713,0.00007059889,0.0002639832,0.0001722658,0.00007888566,0.00009364382,0.000107344,0.00003280359],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.000006981521,"about_ca_system_score_gemma":0.00001981386,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00002150333,"about_ca_topic_score_gemma":0.00001322893,"domain_scores_codex":[0.9991681,0.000246823,0.0001274607,0.0001653429,0.0001535806,0.0001386674],"domain_scores_gemma":[0.9985466,0.0007039167,0.00004133284,0.0006367037,0.0000356017,0.00003584475],"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.0000014016,0.00005163495,0.000009660566,0.000001983568,0.000006710623,0.00006414764,0.0001992328,0.00001826235,0.00001363965,0.9962803,0.0003780441,0.002974957],"study_design_scores_gemma":[0.0001051654,0.00005331814,0.0001140114,0.000004607459,0.000001356971,0.0003154338,0.00007504625,0.007279528,0.002408758,0.9883375,0.001229092,0.00007622082],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.04440283,0.0000238388,0.8153794,0.0004580483,0.0002128586,0.0001119552,0.000002801364,0.00007066807,0.1393376],"genre_scores_gemma":[0.9780259,0.000001392529,0.02073558,0.0007994316,0.000007112236,0.000002892227,1.199078e-7,0.000002517778,0.0004250249],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.9336231,"threshold_uncertainty_score":0.588461,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.05982840385805717,"score_gpt":0.2556288796402041,"score_spread":0.195800475782147,"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."}}