{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:55:41Z","timestamp":1750308941754,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2006,9,1]],"date-time":"2006-09-01T00:00:00Z","timestamp":1157068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2006,9]]},"abstract":"\n Many dynamical systems are\n aggregable<\/jats:italic>\n in the sense that we can divide their variables\n x<\/jats:italic>\n 1<\/jats:sub>\n ,...,\n x<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>\n into several (\n k<\/jats:italic>\n ) non-intersecting groups and find combinations\n y<\/jats:italic>\n 1<\/jats:sub>\n ,...,\n \n y\n k<\/jats:sub>\n <\/jats:italic>\n of variables from these groups (\n macrovariables<\/jats:italic>\n ) whose dynamics depend only on the initial values of the macrovariables. For very large systems, finding such an aggregation is often the only way to perform a meaningful analysis of such systems. Since aggregation is important, researchers have been trying to find a general efficient algorithm for detecting aggregability. In this paper, we show that in general, detecting aggregability is NP-hard even for linear systems, and thus (unless P=NP), we can only hope to find efficient detection algorithms for specific classes of systems.We also show that in the linear case, once the groups are known, it is possible to efficiently find appropriate combinations\n ya<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/1165555.1165556","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T22:35:32Z","timestamp":1161210932000},"page":"97-104","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Aggregability is NP-hard"],"prefix":"10.1145","volume":"37","author":[{"given":"Vladik","family":"Kreinovich","sequence":"first","affiliation":[{"name":"University of Texas at El Paso, El Paso, TX"}]},{"given":"Max","family":"Shpak","sequence":"additional","affiliation":[{"name":"University of Texas at El Paso, El Paso, TX"}]}],"member":"320","published-online":{"date-parts":[[2006,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Decomposability: Queueing and Computer System Applications","author":"Courtois P. J.","year":"1977","unstructured":"P. J. Courtois . Decomposability: Queueing and Computer System Applications . Academic Press , New York , 1977 . P. J. Courtois. Decomposability: Queueing and Computer System Applications. Academic Press, New York, 1977."},{"key":"e_1_2_1_2_1","volume-title":"Computers and Intractability, a Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability, a Guide to the Theory of NP-Completeness . W. H. Freemand and Company , San Francisco , California, 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability, a Guide to the Theory of NP-Completeness. W. H. Freemand and Company, San Francisco, California, 1979."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3800(87)90030-5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/imammb\/6.1.1-a"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:NACO.0000023414.30362.8a"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11513575_10"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1162\/106454605774270624"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02460094"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.thbio.2004.02.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.thbio.2004.04.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/1909285"},{"key":"e_1_2_1_12_1","first-page":"215","article-title":"Equitable partitions, coherent algenras, and random walks: applications to the correlation structure of landscapes","volume":"40","author":"Stadler P. P.","year":"2000","unstructured":"P. P. Stadler and G. Tinhofer . Equitable partitions, coherent algenras, and random walks: applications to the correlation structure of landscapes . MATCH 40 : 215 -- 261 , 2000 . P. P. Stadler and G. Tinhofer. Equitable partitions, coherent algenras, and random walks: applications to the correlation structure of landscapes. MATCH 40:215--261, 2000.","journal-title":"MATCH"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1165555.1165556","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1165555.1165556","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:37:05Z","timestamp":1750282625000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1165555.1165556"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1145\/1165555.1165556"],"URL":"https:\/\/doi.org\/10.1145\/1165555.1165556","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"2006-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}