{"corpus_id":11529237,"paper_sha":"c86de2a41d693c584b4c26d26ae303779dd89091","doi":"10.1109/TIT.1984.1056928","arxiv_id":null,"pmid":null,"pmcid":null,"mag_id":2038603123,"dblp_id":"journals/tit/Arikan84","acl_id":null,"title":"Some complexity results about packet radio networks","year":1983,"publication_date":"1983-03-01","venue":"IEEE Transactions on Information Theory","journal":{"name":"IEEE Trans. Inf. Theory","pages":"681-685","volume":"30"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Computer Science"],"reference_count":4,"citation_count":284,"influential_citation_count":18,"is_open_access":false,"arxiv_categories":null,"arxiv_license":null,"arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"It is shown that the decision problem regarding the membership of a point in the capacity region of a packet radio network is nondeterministic polynomial time hard (NP hard). The capacity region is the set of all feasible origin-to-destination message rates where feasibility is defined as the existence of any set of rules for moving the data through the network so that the desired rates are satisfied.","claims":[{"public_id":"cl_d050d0a8675b17dc50f09e3ec63ba7c0","status":"active","text":"The decision problem regarding membership of a point in the capacity region of a packet radio network is NP hard.","confidence":0.98,"contributors":[{"id":136,"public_id":"3c2apqe3ut","public_label":"Anonymous (3c2apqe3ut)","roles":["extraction"],"url":"https://sah.borca.ai/u/3c2apqe3ut"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/claims/cl_d050d0a8675b17dc50f09e3ec63ba7c0"}],"concepts":[{"public_id":"co_4874fe3102803ab86657dd928e73e712","status":"active","name":"data through the network","description":"The information being moved across the packet radio network according to routing rules.","types":["network entity"],"aliases":[],"contributors":[{"id":136,"public_id":"3c2apqe3ut","public_label":"Anonymous (3c2apqe3ut)","roles":["extraction"],"url":"https://sah.borca.ai/u/3c2apqe3ut"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_4874fe3102803ab86657dd928e73e712"},{"public_id":"co_6a31883c5c5819733f0e7fb82b9115df","status":"active","name":"origin-to-destination message rates","description":"Rates of messages sent from network origins to their destinations.","types":["network quantity"],"aliases":[],"contributors":[{"id":136,"public_id":"3c2apqe3ut","public_label":"Anonymous (3c2apqe3ut)","roles":["extraction"],"url":"https://sah.borca.ai/u/3c2apqe3ut"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_6a31883c5c5819733f0e7fb82b9115df"},{"public_id":"co_7481c962cc343eabf3c2e42b1493b350","status":"active","name":"packet radio networks","description":"Networks considered for moving packetized data from origins to destinations.","types":["network model"],"aliases":[],"contributors":[{"id":136,"public_id":"3c2apqe3ut","public_label":"Anonymous (3c2apqe3ut)","roles":["extraction"],"url":"https://sah.borca.ai/u/3c2apqe3ut"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_7481c962cc343eabf3c2e42b1493b350"},{"public_id":"co_770d5432593f9e0b3fcf623df47ebf67","status":"active","name":"feasible origin-to-destination message rates","description":"Message rates that can be satisfied by some rules for moving data through the network.","types":["network quantity"],"aliases":[],"contributors":[{"id":136,"public_id":"3c2apqe3ut","public_label":"Anonymous (3c2apqe3ut)","roles":["extraction"],"url":"https://sah.borca.ai/u/3c2apqe3ut"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_770d5432593f9e0b3fcf623df47ebf67"},{"public_id":"co_97af38b3778c1d203417d7200ed45aa9","status":"active","name":"rules for moving the data through the network","description":"Procedures or policies that determine how data is routed or transferred through the packet radio network.","types":["network procedure"],"aliases":[],"contributors":[{"id":136,"public_id":"3c2apqe3ut","public_label":"Anonymous (3c2apqe3ut)","roles":["extraction"],"url":"https://sah.borca.ai/u/3c2apqe3ut"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_97af38b3778c1d203417d7200ed45aa9"},{"public_id":"co_a93abf9e2928fd1effbbec96a89fc6a3","status":"active","name":"nondeterministic polynomial time hard","description":"A computational hardness classification applied to the capacity-region membership decision problem.","types":["complexity class"],"aliases":["NP hard"],"contributors":[{"id":136,"public_id":"3c2apqe3ut","public_label":"Anonymous (3c2apqe3ut)","roles":["extraction"],"url":"https://sah.borca.ai/u/3c2apqe3ut"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_a93abf9e2928fd1effbbec96a89fc6a3"},{"public_id":"co_bff1a6dece97d9626d51479f39dd2f78","status":"active","name":"decision problem regarding membership of a point","description":"The computational question of whether a given point belongs to a specified capacity region.","types":["computational problem"],"aliases":[],"contributors":[{"id":136,"public_id":"3c2apqe3ut","public_label":"Anonymous (3c2apqe3ut)","roles":["extraction"],"url":"https://sah.borca.ai/u/3c2apqe3ut"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_bff1a6dece97d9626d51479f39dd2f78"},{"public_id":"co_e38ea36f02e7fb9d6e06a7c97e20606b","status":"active","name":"capacity region","description":"The set of feasible origin-to-destination message rates in a packet radio network.","types":["mathematical object"],"aliases":[],"contributors":[{"id":136,"public_id":"3c2apqe3ut","public_label":"Anonymous (3c2apqe3ut)","roles":["extraction"],"url":"https://sah.borca.ai/u/3c2apqe3ut"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_e38ea36f02e7fb9d6e06a7c97e20606b"}],"external_ids":{"DOI":"10.1109/TIT.1984.1056928","ArXiv":null,"PubMed":null,"PubMedCentral":null,"MAG":2038603123,"DBLP":"journals/tit/Arikan84","ACL":null},"open_access":{"is_open_access":false,"pdf_url":null,"landing_url":"https://sah.borca.ai/papers/11529237","source":null,"pdf_url_source":null,"license":null,"reason":"pdf_url_not_indexed"},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":false,"full_text_source":null,"count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":630961,"paper_uid":"2b72f283-31dd-4562-8626-707b2d3002d8","canonical_identity":{"paper_id":630961,"paper_uid":"2b72f283-31dd-4562-8626-707b2d3002d8","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/11529237"}