{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T19:34:21Z","timestamp":1772652861219,"version":"3.50.1"},"reference-count":30,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2002,12]]},"abstract":"<jats:p> We exhibit finite algebras each generating a variety with NP-complete finite algebra membership problem. The smallest of these algebras is the flat graph algebra belonging to the tetrahedral graph, a graph of 6 vertices obtained by cutting and spreading out the surface of a tetrahedron on the plane. The sequence of graphs we use to build up our flat graph algebras is similar to the sequence exhibited by Wheeler in [36] , 1979, to describe the first order theory of k-colorable graphs. Graph algebras were introduced by Shallon in [34] , 1979, and investigated, among others, by Baker, McNulty and Werner in [2] , 1987. Flat algebras were constructed and used by McKenzie in [27] , 1996, to settle some open questions related to decidability, like Tarski's Finite Basis Problem. Flat graph algebras were also discussed by Willard in [37] , 1996, and Deli\u0107 in [8] , 1998. <\/jats:p>","DOI":"10.1142\/s0218196702001085","type":"journal-article","created":{"date-parts":[[2002,12,20]],"date-time":"2002-12-20T11:13:16Z","timestamp":1040382796000},"page":"811-823","source":"Crossref","is-referenced-by-count":17,"title":["COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES"],"prefix":"10.1142","volume":"12","author":[{"given":"ZOLT\u00c1N","family":"SZ\u00c9KELY","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Gallaudet University, 800 Florida Ave. NE, Washington, DC 20002, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(77)90056-1"},{"key":"p_2","first-page":"3","volume":"51","author":"Baker K.","year":"1987","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"p_5","first-page":"379","volume":"180","author":"Berman J.","year":"1996","journal-title":"Lecture Notes in Pure and Applied Mathematics"},{"key":"p_6","first-page":"269","author":"Bleichenbacher D.","year":"1990","journal-title":"Gordon and Breach Sci. Publ."},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19950410204"},{"key":"p_9","first-page":"121","volume":"2","author":"Demel J.","year":"1982","journal-title":"Kybernetika"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90042-8"},{"key":"p_12","first-page":"273","author":"Goral\u010d\u00edk P.","year":"1980","journal-title":"New York"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(96)00050-3"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80053-3"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1952-0047584-3"},{"key":"p_17","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"New York"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196795000227"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(73)90025-2"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1137\/0217043"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1951-0044470-3"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1954-0060482-6"},{"key":"p_24","doi-asserted-by":"crossref","first-page":"24","DOI":"10.7146\/math.scand.a-10984","volume":"27","author":"R","year":"1970","journal-title":"Math. Scand."},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01195263"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196796000027"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196796000040"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1016\/0747-7171(92)90013-T"},{"key":"p_30","first-page":"815","volume":"163","author":"Murski V. L.","year":"1965","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(64)90004-3"},{"key":"p_32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02483103"},{"key":"p_33","first-page":"293","volume":"11","author":"Perkins P.","year":"1968","journal-title":"J. Algebra"},{"key":"p_35","first-page":"724","volume":"4","author":"Visin V. V.","year":"1963","journal-title":"Soviet Math. Dokl."},{"key":"p_36","first-page":"289","volume":"250","author":"Wheeler W. H.","year":"1979","journal-title":"Trans. Amer. Math. Soc."},{"key":"p_37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01879739"},{"key":"p_38","first-page":"335","volume":"45","author":"Willard R.","year":"2001","journal-title":"Algebra Universalis"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196702001085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T21:56:37Z","timestamp":1565128597000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196702001085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,12]]},"references-count":30,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2002,12]]}},"alternative-id":["10.1142\/S0218196702001085"],"URL":"https:\/\/doi.org\/10.1142\/s0218196702001085","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,12]]}}}