{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T19:01:29Z","timestamp":1648753289514},"reference-count":35,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[1984,12,1]],"date-time":"1984-12-01T00:00:00Z","timestamp":470707200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[1984,12]]},"DOI":"10.1016\/0196-6774(84)90010-5","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T03:44:36Z","timestamp":1108007076000},"page":"595-609","source":"Crossref","is-referenced-by-count":1,"title":["The NP-completeness column: An ongoing guide"],"prefix":"10.1016","volume":"5","author":[{"given":"David S","family":"Johnson","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0196-6774(84)90010-5_BIB1","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1145\/322186.322200","article-title":"Lower bounds on information transfer in distributed computations","volume":"27","author":"Abelson","year":"1980","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(84)90010-5_BIB2","series-title":"Proceedings 9th Ann. ACM Symp. on Theory of Computing","first-page":"151","article-title":"Reducibility, randomness and intractability","author":"Adleman","year":"1977"},{"key":"10.1016\/0196-6774(84)90010-5_BIB3","series-title":"Proceedings 20th Ann. Symp. on Foundations of Computer Science","first-page":"397","article-title":"Reductions that lie","author":"Adleman","year":"1979"},{"key":"10.1016\/0196-6774(84)90010-5_BIB4","doi-asserted-by":"crossref","first-page":"884","DOI":"10.1109\/TCOM.1984.1096151","article-title":"Deadlock-resistant flow control procedures for store-and-forward networks","author":"Blazewics","year":"1984","journal-title":"IEEE Trans. Communication"},{"key":"10.1016\/0196-6774(84)90010-5_BIB5","series-title":"Proceedings 2nd ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing","first-page":"254","article-title":"Scheduling file transfers in a distributed network","author":"Coffman","year":"1983"},{"key":"10.1016\/0196-6774(84)90010-5_BIB6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1109\/TC.1984.1676417","article-title":"Testing the coordination predicate","author":"Cuny","year":"1984","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0196-6774(84)90010-5_BIB7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0020-0190(79)90105-4","article-title":"Implicit computation of synchronization primitives","volume":"9","author":"DeMillo","year":"1979","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(84)90010-5_BIB8","series-title":"On finding deadlocks in protocols","author":"DeTreville","year":"1982"},{"key":"10.1016\/0196-6774(84)90010-5_BIB9","series-title":"Programming Languages","first-page":"43","article-title":"Cooperating sequential processes","author":"Dijkstra","year":"1968"},{"key":"10.1016\/0196-6774(84)90010-5_BIB10","series-title":"Proceedings 16th Ann. ACM Symp. on Theory of Computing","first-page":"81","article-title":"Lower bounds on communication complexity","author":"Duris","year":"1984"},{"key":"10.1016\/0196-6774(84)90010-5_BIB11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230140102","article-title":"On the NP-completeness of certain network testing problems","volume":"14","author":"Even","year":"1984","journal-title":"Networks"},{"key":"10.1016\/0196-6774(84)90010-5_BIB12","series-title":"Proceedings 16th Ann. ACM Symp. on Theory of Computing","first-page":"493","article-title":"The impact of synchronous communication on the problem of electing a leader in a ring","author":"Frederickson","year":"1984"},{"key":"10.1016\/0196-6774(84)90010-5_BIB13","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1109\/TC.1978.1674966","article-title":"On the computational complexity of system diagnosis","author":"Fujiwara","year":"1978","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0196-6774(84)90010-5_BIB14","series-title":"Proceedings 22nd Ann. Symp. on Foundations of Computer Science","first-page":"150","article-title":"Symmetry breaking in distributed networks","author":"Itai","year":"1981"},{"key":"10.1016\/0196-6774(84)90010-5_BIB15","series-title":"Scheduling with simultaneous resource requirements","author":"Johnson","year":"1984"},{"key":"10.1016\/0196-6774(84)90010-5_BIB16","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0022-0000(80)90033-1","article-title":"The complexity of problems in systems of communicating sequential processes","volume":"21","author":"Ladner","year":"1980","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0196-6774(84)90010-5_BIB17","article-title":"\u2018Global\u2019 graph problems tend to be intractable","author":"Lakshmipathy","year":"1984"},{"key":"10.1016\/0196-6774(84)90010-5_BIB18","series-title":"Proceedings 13th Ann. ACM Symp. on Theory of Computing","first-page":"300","article-title":"Lower bounds for VLSI","author":"Lipton","year":"1981"},{"key":"10.1016\/0196-6774(84)90010-5_BIB19","series-title":"Proceedings 14th Ann. ACM Symp. on Theory of Computing","first-page":"330","article-title":"Las Vegas is better than determinism in VLSI and distributed computing","author":"Mehlhorn","year":"1982"},{"key":"10.1016\/0196-6774(84)90010-5_BIB20","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1109\/TC.1976.5009249","article-title":"On models for diagnosable systems and probabilistic fault diagnosis","author":"Maheshwari","year":"1976","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/0196-6774(84)90010-5_BIB21","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","article-title":"Communication complexity","volume":"28","author":"Papadimitriou","year":"1984","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0196-6774(84)90010-5_BIB22","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0019-9958(82)91034-8","article-title":"On the complexity of designing distributed protocols","volume":"53","author":"Papadimitriou","year":"1982","journal-title":"Information and Control"},{"key":"10.1016\/0196-6774(84)90010-5_BIB23","series-title":"Proceedings 25th Ann. Symp. on Foundations of Computer Science","article-title":"Probabilistic communication complexity","author":"Paturi","year":"1984"},{"key":"10.1016\/0196-6774(84)90010-5_BIB24","series-title":"Proceedings 25th Ann. Symp. on Foundations of Computer Science","article-title":"A polynomial time algorithm for fault diagnosability","author":"Sullivan","year":"1984"},{"key":"10.1016\/0196-6774(84)90010-5_BIB25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF00263928","article-title":"Complexity of analyzing the synchronization structure of concurrent programs","volume":"19","author":"Taylor","year":"1983","journal-title":"Acta Inform."},{"key":"10.1016\/0196-6774(84)90010-5_BIB26","series-title":"Proceedings 11th Ann. ACM Symp. on Theory of Computing","first-page":"81","article-title":"Area-time complexity for VLSI","author":"Thompson","year":"1979"},{"key":"10.1016\/0196-6774(84)90010-5_BIB27","article-title":"A Complexity Theory for VLSI","author":"Thompson","year":"1980"},{"key":"10.1016\/0196-6774(84)90010-5_BIB28","series-title":"Proceedings 11th Ann. ACM Symp. on Theory of Computing","first-page":"89","article-title":"Deadlock-free packet switching networks","author":"Toueg","year":"1979"},{"key":"10.1016\/0196-6774(84)90010-5_BIB29","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1137\/0210053","article-title":"Some complexity results in the design of deadlock-free packet switching networks","volume":"10","author":"Toueg","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0196-6774(84)90010-5_BIB30","series-title":"Computational Aspects of VLSI","author":"Ullman","year":"1984"},{"key":"10.1016\/0196-6774(84)90010-5_BIB31","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(83)90004-X","article-title":"A natural encoding scheme proved probabilistic polynomial complete","volume":"24","author":"Vazirani","year":"1983","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/0196-6774(84)90010-5_BIB32","series-title":"Proceedings 24th Ann. Symp. on Foundations of Computer Science","first-page":"146","article-title":"Trade-offs between depth and width in parallel computation","author":"Vishkin","year":"1983"},{"key":"10.1016\/0196-6774(84)90010-5_BIB33","series-title":"Proceedings 21st Ann. Symp. on Foundations of Computer Science","first-page":"294","article-title":"A combinatorial limit to the computing power of V.L.S.I. circuits","author":"Vuillemin","year":"1980"},{"key":"10.1016\/0196-6774(84)90010-5_BIB34","series-title":"Proceedings 11th Ann. ACM Symp. on Theory of Computing","first-page":"209","article-title":"Some complexity questions related to distributive computing","author":"Yao","year":"1979"},{"key":"10.1016\/0196-6774(84)90010-5_BIB35","series-title":"Proceedings 13th Ann. ACM Symp. on Theory of Computing","first-page":"308","article-title":"The entropic limitations on VLSI computations","author":"Yao","year":"1981"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677484900105?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677484900105?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T01:26:41Z","timestamp":1548725201000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677484900105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,12]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1984,12]]}},"alternative-id":["0196677484900105"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(84)90010-5","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1984,12]]}}}