{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:13Z","timestamp":1759638373028},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p> We study the computational complexity of the HIDDEN SUBGROUP problem, a well-studied problem in quantum computing. First we show that several proposed generalizations or variants of this problem, including HIDDEN COSET, HIDDEN SHIFT, and ORBIT COSET, are all equivalent or reducible to HIDDEN SUBGROUP. Then we study the relationship between the decision version and search version of HIDDEN SUBGROUP over various group classes. We show that the two versions are polynomial-time equivalent over permutation groups, and over dihedral groups given the order of the group is smooth. Finally, we give nonadaptive program checkers for HIDDEN SUBGROUP and its decision version. <\/jats:p>","DOI":"10.1142\/s0129054113500305","type":"journal-article","created":{"date-parts":[[2014,4,2]],"date-time":"2014-04-02T06:43:49Z","timestamp":1396421029000},"page":"1221-1234","source":"Crossref","is-referenced-by-count":2,"title":["ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM"],"prefix":"10.1142","volume":"24","author":[{"given":"STEPHEN","family":"FENNER","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of South Carolina, Columbia, SC 29208, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YONG","family":"ZHANG","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Kutztown University of Pennsylvania, Kutztown, PA 19530, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,4]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1125"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00159-6"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228289"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.82.1"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1985.0070"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1992.0167"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2000.0699"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.024"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0009-8"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970139450X"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90004-8"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298637"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113500305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:48:20Z","timestamp":1565200100000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113500305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":14,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2014,4]]},"published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1142\/S0129054113500305"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113500305","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}