On the number of queries necessary to identify a permutation |
| |
| Authors: | Ker-I Ko Shia-Chung Teng |
| |
| Affiliation: | 1. CSIR-Central Institute of Medicinal and Aromatic Plants (CSIR-CIMAP), Kukrail Picnic Spot Road, P.O. CIMAP, Lucknow 226015, India;2. CSIR-Indian Institute of Integrative Medicine (CSIR-IIIM), Canal Road, Jammu 180001, India;3. CSIR-Central Drug Research Institute (CSIR-CDRI), B.S. 10/1, Sector 10, Jankipuram Extension, Sitapur Road, Lucknow 226031, India;1. Departamento de Matemática, Facultad de Ciencias, Universidad de Tarapacá, Arica, Chile;2. Faculty of Mathematics and Informatics, Shumen University, Bulgaria;3. Institute of Applied Statistics and Linz Institute of Technology, Johannes Kepler University in Linz, Altenberger Straße 69, A-4040, Linz a. D., Austria;4. Institute of Statistics, University of Valparaíso, Valparaíso, Chile;5. School of Mathematics & Statistical Sciences, Arizona State University, Tempe, AZ, USA;6. Department of Statistics and Operation Analysis, Mendel University in Brno, Czech Republic;7. Facultad de Ingeniería, Universidad Andres Bello, Chile;1. Department of Civil Engineering, Saroyeh University, P.O. Box 404, Sari, Iran;2. Young Researchers and Elite Club, Qaemshahr Branch, Islamic Azad University, Qaemshahr, Iran;3. Assistant Professor of Department of Civil Engineering, Islamic Azad University, Qaemshahr, Iran;1. National Research Nuclear University MEPhI (Moscow Engineering Physics Institute), Kashirskoe Shosse 31, 115409, Moscow, Russia;2. Forschungszentrum Jülich GmbH, Institut für Energie- und Klimaforschung, 52425, Jülich, Germany;1. Department of Mathematics and Computer Science, University of Lethbridge, 4401 University Drive, Lethbridge, Alberta, T1K 3M4, Canada;2. National Center for Theoretical Sciences, No. 1, Sec. 4, Roosevelt Rd., Taipei City, Taiwan |
| |
| Abstract: | Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log2n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log2n). |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
