{"id":"W2004536047","doi":"10.5555/365411.365806","title":"On universally easy classes for NP-complete problems","year":2001,"lang":"en","type":"article","venue":"","topic":"Advanced Graph Theory Research","field":"Computer Science","cited_by":1,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of New Brunswick; University of Waterloo","funders":"","keywords":"Intersection (aeronautics); Time complexity; NP-complete; Computer science; P versus NP problem; Mathematics; Polynomial; Regular language; Discrete mathematics; Theoretical computer science; Combinatorics; Automaton","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.006537583,0.001694654,0.002127688,0.003956982,0.004744254,0.009918581,0.003439952,0.00342416,0.009410855],"category_scores_gemma":[0.03198352,0.001649639,0.003751168,0.003586065,0.01109318,0.02823202,0.01117847,0.01268427,0.001067348],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003800997,"about_ca_system_score_gemma":0.001587561,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0019189,"about_ca_topic_score_gemma":0.001278505,"domain_scores_codex":[0.9901462,0.002380832,0.0007107112,0.002717572,0.002580338,0.001464377],"domain_scores_gemma":[0.9578591,0.03485473,0.001981272,0.002664956,0.00119182,0.001448091],"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.0001081741,0.0001517151,0.001866595,0.0003188229,0.00004100231,0.0002381632,0.0009152447,0.006168269,0.0008864738,0.9625649,0.003596135,0.0231444],"study_design_scores_gemma":[0.00002834549,0.0000383528,0.0006028687,0.00007307439,0.00002939476,0.000233684,0.0003475981,0.01102235,0.0005035465,0.9806583,0.006430259,0.00003222888],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1169881,0.005504546,0.7919891,0.01494716,0.0004433595,0.0004316847,0.001097301,0.001358997,0.06723985],"genre_scores_gemma":[0.748521,0.005390888,0.2204398,0.003526448,0.003683992,0.001136916,0.002760889,0.0007417215,0.01379838],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.009918581,"threshold_uncertainty_score":0.03457445,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.05071034637469949,"score_gpt":0.3023161627498708,"score_spread":0.2516058163751713,"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."}}