{"public_id":"co_d545771e92c20a3064a52d0a0d044188","status":"active","merged_into_public_id":null,"resolved_public_id":"co_d545771e92c20a3064a52d0a0d044188","name":"f(k)n^{o(d/log d)}","description":"A forbidden running-time form combining an arbitrary computable function of k with a subpolynomial factor in n relative to d/log d.","aliases":[],"types":["time complexity"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"origin_summary":{"object_type":"concept","status":"active","confidence":null,"origin_kinds":["extraction_create"],"contribution_count":1,"contribution_task_types":["extraction"],"contribution_statuses":["applied"],"verifier_verdict_count":0,"verifier_classes":[],"verifier_class_counts":{"system":0,"user_agent":0},"verdict_counts":{"approve":0,"reject":0},"verifier_state":"no_verdicts","basis":["kg_settlement_results.decision_payload.legacy_bridge","kg_entity_origin_refs","kg_assertion_proposals","contributions","verifications","concept.status"],"limits":["ledger provenance is aggregated; raw contribution and verifier audit rows are not expanded","entity matching uses settlement bridge refs and edge commands"]},"papers":[{"corpus_id":3046746,"title":"Routing with Congestion in Acyclic Digraphs","citation_count":16,"url":"https://sah.borca.ai/papers/3046746"}],"claims":[{"public_id":"cl_0017f1ba2509a2978c4d2e2ce414d546","text":"Under a suitable complexity-theoretic assumption, the problem has no algorithm with running time f(k)n^{o(d/log d)} for any computable function f.","corpus_id":3046746,"url":"https://sah.borca.ai/claims/cl_0017f1ba2509a2978c4d2e2ce414d546"}],"related_concepts":[],"resolved_url":"https://sah.borca.ai/concepts/co_d545771e92c20a3064a52d0a0d044188","url":"https://sah.borca.ai/concepts/co_d545771e92c20a3064a52d0a0d044188"}