{"schema_version":"4ort.packet/1","entity":{"entity_id":"computational-complexity","kg_uuid":"0e0ce53e-6b13-4aa0-bdde-cb6113fab6f5","wikidata_id":"Q5157286","name":"computational complexity","description":"measure of the amount of resources needed to run an algorithm or solve a computational problem","type":"Intangible","url":"https://4ort.xyz/entity/computational-complexity"},"status":"complete","as_of":{"copy_written_at":"2026-11-15T14:27:42Z","last_source_edit_seen":"2026-06-05T07:01:46Z","stale_possible":false,"claims_refreshed_at":"2026-10-25T11:48:00Z","source_revision":2534776717},"facts":[{"field":"P31","label":"instance of","value":"concept","value_id":"Q151885","value_raw":"Q151885","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P31","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P279","label":"subclass of","value":"measure","value_id":"Q39875001","value_raw":"Q39875001","rank":"normal","current":null,"qualifiers":[{"field":"P1013","label":"criterion used","value":"computational resource"},{"field":"P13044","label":"characteristic of","value":"computational problem"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P279","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1343","label":"described by source","value":"Computability and Complexity Theory","value_id":"Q110973357","value_raw":"Q110973357","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P1343","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1482","label":"Stack Exchange tag","value":"https://math.stackexchange.com/tags/computational-complexity","value_id":null,"value_raw":"https://math.stackexchange.com/tags/computational-complexity","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P1482","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1482","label":"Stack Exchange tag","value":"https://mathoverflow.net/tags/computational-complexity","value_id":null,"value_raw":"https://mathoverflow.net/tags/computational-complexity","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P1482","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1482","label":"Stack Exchange tag","value":"https://cs.stackexchange.com/tags/complexity-theory","value_id":null,"value_raw":"https://cs.stackexchange.com/tags/complexity-theory","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P1482","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1482","label":"Stack Exchange tag","value":"https://cstheory.stackexchange.com/tags/complexity","value_id":null,"value_raw":"https://cstheory.stackexchange.com/tags/complexity","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P1482","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1687","label":"main Wikidata property","value":"P10374","value_id":null,"value_raw":"P10374","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P1687","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1889","label":"different from","value":"big O notation","value_id":"Q269878","value_raw":"Q269878","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P1889","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[{"imported_from":"Polish Wikipedia"}]},"trust":{"band":"medium","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P1889","label":"different from","value":"asymptotic computational complexity","value_id":"Q13414364","value_raw":"Q13414364","rank":"normal","current":null,"qualifiers":[{"field":"P3831","label":"object of statement has role","value":"subclass"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P1889","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2579","label":"studied by","value":"computational complexity theory","value_id":"Q205084","value_raw":"Q205084","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P2579","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2579","label":"studied by","value":"analysis of algorithms","value_id":"Q333464","value_raw":"Q333464","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P2579","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2579","label":"studied by","value":"theory of computation","value_id":"Q844718","value_raw":"Q844718","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P2579","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P2924","label":"Great Russian Encyclopedia Online ID (2017)","value":"1810355","value_id":null,"value_raw":"1810355","rank":"normal","current":null,"qualifiers":[{"field":"P1810","label":"subject named as","value":"АЛГОРИТМА СЛОЖНОСТЬ"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P2924","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P3235","label":"PhilPapers topic","value":"computational-complexity","value_id":null,"value_raw":"computational-complexity","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P3235","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P5106","label":"Dictionary of Algorithms and Data Structures ID","value":"complexity","value_id":null,"value_raw":"complexity","rank":"normal","current":null,"qualifiers":[{"field":"P1810","label":"subject named as","value":"complexity"}],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P5106","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P11514","label":"Great Russian Encyclopedia portal ID","value":"slozhnost-algoritma-32c462","value_id":null,"value_raw":"slozhnost-algoritma-32c462","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P11514","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}},{"field":"P12946","label":"FOLDOC ID","value":"computational+complexity","value_id":null,"value_raw":"computational+complexity","rank":"normal","current":null,"qualifiers":[],"layer":"source","citation":{"source":"wikidata","source_name":"Wikidata","source_record":"https://www.wikidata.org/wiki/Q5157286#P12946","source_edition":"2026-10-25T11:48:00Z","edition_basis":"claims_refreshed_at","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"references":[]},"trust":{"band":"unscored","basis":"wikidata-reference-support/2","calibrated":false}}],"unknowns":[],"omitted":{"facts":0,"reason":null},"licences":[{"source":"wikidata","source_name":"Wikidata","licence":"CC0 1.0 Universal","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/","attribution":null,"fields":["P31","P279","P1343","P1482","P1687","P1889","P2579","P2924","P3235","P5106","P11514","P12946"]}],"routes":{"entity_page":"https://4ort.xyz/entity/computational-complexity","packet_api":"https://4ort.xyz/api/v1/entities/computational-complexity/packet","facts_jsonld":"https://4ort.xyz/entity/computational-complexity/facts.json","changes_api":"https://4ort.xyz/api/v1/knowledge/get_entity_changes?entity=computational-complexity","attention_api":"https://4ort.xyz/api/v1/knowledge/get_attention?entity=computational-complexity","wikidata":"https://www.wikidata.org/wiki/Q5157286","official_website":null},"trust_rules":{"wikidata-reference-support/2":"From the references in our copy of the statement: high = it cites a source (stated in P248, or a reference URL that is not Wikipedia); medium = only 'imported from Wikimedia project' or a Wikipedia URL; unscored = our copy holds no reference (older copies dropped references, so this is not evidence that Wikidata has none). Wikidata may hold more references than our copy shows. Reference support, not a probability."},"notes":[]}