Рассмотрен количественный аналог проблемы декодирования по принципу максимального правдоподобия. Установлена экономная сводимость от проблемы совершенного паросочетания и слабо экономная сводимость от проблемы максимального разреза. Показана полнота в классах WPP, С=Р и РР для некоторых количественных вариантов проблемы декодирования по принципу максимального правдоподобия.
- Title О проблеме декодирования по принципу максимального правдоподобия
- Headline О проблеме декодирования по принципу максимального правдоподобия
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 70
- Date:
- DOI 10.17223/20710410/70/1
Ключевые слова
вычислительная сложность, проблема декодирования по принципу максимального правдоподобия, проблема совершенного паросочетания, проблема максимального разрезаАвторы
Ссылки
Berlekamp Е., McEliece R., and van Tilborg Н. On the inherent intractability of certain coding problems (Corresp.) // IEEE Trans. Inform. Theory. 1978. V. 24. No.3. P.384-386.
McEliece R. J. A public-key cryptosystem based on algebraic coding theory // Deep Space Network Progress Report. 1978. V. 42. No. 44. P.114-116.
Kichna A. and Farchane A. A survey on various decoding algorithms for McEliece cryptosystem based on QC-MDPC codes // Proc. IRASET. Mohammedia, Morocco, 2023. P. 1-7.
Liu J., Tong X., Wang Z., et al. An improved McEliece cryptosystem based on QC-MDPC code with compact key size // Telecommun. Svst. 2022. V. 80. P. 17-32.
Lau T. and Tan C. On the design and security of Lee metric McEliece cryptosystems // Des. Codes Crvptogr. 2022. V. 90. No. 3. P. 695-717.
https://www.nist.gov/programs-projects/post-quantum-cryptography. 2024.
https://classic.mceliece.org/. 2024.
https://web.archive.org/web/20171229103229/https://nts-kem.іо/. 2024.
Niederreiter H. Knapsack-tvpe cryptosystems and algebraic coding theory // Problems Control Inform. Theory. 1986. V. 15. No. 2. P. 159-166.
Dent A. W. A designer’s guide to KEMs // LNCS. 2003. V.2898. P. 133-151.
Fujisaki E. and Okamoto T. Secure integration of asymmetric and symmetric encryption schemes // J. Cryptology. 2013. V. 26. No. 1. P.80-101.
Fajita Н. Quantum МсЕПесе public-key cryptosystem // Quantum Inform. & Comput. 2012. V. 12. No. 3-4. P. 181-202.
Oh Y., Jang K., him S., et al. Quantum implementation of core operations in classic McEliece // Proc. PlatCon. Busan, Korea, 2023. P.67-72.
Fuentes P., Martinez J. E., Crespo P. M., and Garcia-Frias J. Degeneracy and its impact on the decoding of sparse quantum codes // IEEE Access. 2021. V. 9. P. 89093-89119.
Kubica A. and Vasmer M. Single-shot quantum error correction with the three-dimensional subsystem toric code // Nat.Commun. 2022. V. 13. Article No. 6272.
Kuo K.-Y. and Lai C.-Y. Exploiting degeneracy in belief propagation decoding of quantum codes // npj Quantum Inform. 2022. V. 8. Article No. 111.
Elbro F. and Majenz C. An algebraic attack against McEliece-like cryptosystems based on BCH codes // Proc. ITW. Saint-Malo, Prance, 2023. P.70-75.
Gray H., Battarbee C., Shahandashti S. F., and Kahrobaei D. A novel attack on McEliece’s cryptosystem // Intern. J.Computer Math.: Computer Systems Theory. 2023. V. 8. No. 3. P.178-191.
Kirshanova E. and May A. Breaking Goppa-based McEliece with hints // Inform.Comput. 2023. V. 293. Article No. 105045.
Baldi M., Bianchi M., and Chiaraluce F. Security and complexity of the McEliece cryptosystem based on quasi-cvclic low-density parity-check codes // IET Inform. Security. 2013. V. 7. No. 3. P.212-220.
Freudenberger J. and Thiers J. P. A new class of Q-ary codes for the McEliece cryptosystem // Cryptography. 2021. V. 5. No. 1. Article No. 11.
Mariot L., Picek S., and Yorgova R. On McEliece-type cryptosystems using self-dual codes with large minimum weight // IEEE Access. 2023. V. 11. P.43511-43519.
Hsieh M.-H. and Le Gall F. NP-hardness of decoding quantum error-correction codes // Phvs. Rev. A. 2011. V. 83. Article No. 052331.
Kuo K.-Y. and Lu C.-C. On the hardness of decoding quantum stabilizer codes under the depolarizing channel // Intern. Svmp. Inform. Theory and its Appl. Honolulu, USA, 2012. P.208-211.
Kuo K.-Y. and Lu C.-C. On the hardnesses of several quantum decoding problems // Quantum Inf. Process. 2020. V. 19. Article No. 123.
Iyer P. and Poulin D. Hardness of decoding quantum stabilizer codes // IEEE Trans. Inform. Theory. 2015. V.61. No.9. P.5209-5223.
Kuo K.-Y. and Lai C.-Y. The encoding and decoding complexities of entanglement-assisted quantum stabilizer codes // Proc ISIT. Paris, France, 2019. P. 2893-2897.
Chamberland C., Goncalves L., Sivarajah P., et al. Techniques for combining fast local decoders with global decoders under circuit-level noise // Quantum Sci. Technology. 2023. V. 8. Article No. 045011.
Hammar K., Orekhov A., Hybelius P. W., et al. Error-rate-agnostic decoding of topological stabilizer codes // Phvs. Rev. A. 2022. V. 105. Article No. 042616.
Theveniaut H. and van Nieuwenburg E. A NEAT quantum error decoder // SciPost Physics. 2021. V. 11. Article No. 005.
Colomer L. D., Skotiniotis M., and Munoz-Tapia R. Reinforcement learning for optimal error correction of toric codes // Phvs. Let. A. 2020. V.384. No. 17. Article 126353.
Sweke R., Kesselring M. S., van Nieuwenburg E. P. L., and Eisert J. Reinforcement learning decoders for fault-tolerant quantum computation // Mach. Learn.: Sci. Technol. 2021. V. 2. Article No. 025005.
Krastanov S. and Jiang L. Deep neural network probabilistic decoder for stabilizer codes // Sci. Rep. 2017. V.7. Article No. 11003.
Baireuther P., Cato M. D., Criger B., et al. Neural network decoder for topological color codes with circuit level noise // New J. Physics. 2019. V. 21. Article No. 013003.
Gicev S., Hollenberg L. C. L., and Usman M. A scalable and fast artificial neural network syndrome decoder for surface codes // Quantum. 2023. V. 7. Article No. 1058.
Bordoni S. and Giagu S. Convolutional neural network based decoders for surface codes // Quantum Inf. Process. 2023. V.22. Article No. 151.
Li A., Li F., Gan Q., and Ma H. Convolutional-Neural-Network-Based hexagonal quantum error correction decoder // Appl. Sci. 2023. V. 13. No. 17. Article 9689.
Wenger E., Chen M., Charton F., and Lauter K. SALSA: Attacking Lattice Cryptography with Transformers. Cryptology ePrint Archive. 2022. Paper 2022/935. https://eprint.iacr.org/2022/935.
Brack J. and Naor M. The hardness of decoding linear codes with preprocessing // IEEE Trans. Inform. Theory. 1990. V.36. No. 2. P.381-385.
Burner I., Micciancio D., and Sudan M. Hardness of approximating the minimum distance of a linear code // IEEE Trans. Inform. Theory. 2003. V.49. No. 1. P.22-37.
Vardy A. The intractability of computing the minimum distance of a code // IEEE Trans. Inform. Theory. 1997. V.43. No. 6. P.1757-1766.
Papadimitriou C.H.Computational Complexity. Reading, Addison-Weslev, 1994. 523 p.
Juban L. Dichotomy theorem for the generalized unique satisfiability problem // LNCS. 1999. V. 1684. P. 327-337.
Creignou N. and Hermann M.Complexity of generalized satisfiability counting problems // Inform.Comput. 1996. V. 125. No. 1. P. 1-12.
Valiant L. G. The complexity of computing the permanent // Theoretical Computer Sci. 1979. V. 8. No. 2. P.189-201.
Barbanchon R. On unique graph 3-colorabilitv and parsimonious reductions in the plane // Theoretical Computer Sci. 2004. V. 319. No. 1-3. P. 455-482.
Karp R.M. Reducibilitv among combinatorial problems // R. E. Miller, J.W. Thatcher, and J.D. Bohlinger (eds.).Complexity of Computer Computations. The IBM Research Symposia Series. Boston: Springer, 1972. P.85-103.
Garey M. R. and Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman, 1979. 338 p.
Garey M.R., Johnson D.S., and Stockmeyer L. Some simplified NP-complete graph problems // Theoretical Computer Sci. 1976. V. 1. No.3. P.237-267.
Brack J. and Blaum M. Neural networks, error-correcting codes, and polynomials over the binary n-cube // IEEE Trans. Inform. Theory. 1989. V. 35. No. 5. P.976-987.
Барг С. Некоторые новые NP-полные задачи кодирования j j Проблемы передачи информации. 1994. Т.30. №3. С.23-28.
Jelínková, O. Suchý, P. Hliněný, J. Kratochvíl Parameterized problems related to Seidel’s switching // Discrete Math. Theoretical Computer Sci. 2011. V. 13. No. 2. P. 19-42.
Tanatmis A. Mathematical Programming Approaches for Decoding of Binary Linear Codes. Vom Fachbereich Mathematik der Technischen Universitat Kaiserslautern zur Erlangung des akademischen Grades Doktor der Naturwissenschaften (Doctor rerum naturalium, Dr. rer. nat.) genehmigte Dissertation, 2011.
Arora S., Babai L., Stern J., and Sweedyk Z. The hardness of approximate optima in lattices, codes, and systems of linear equations // J.Computer System Sci. 1997. V. 54. No. 2. P.317-331.
Lindell Y.Introduction to Coding Theory, https://yehudalindell.com/teaching/introduction-to-coding-theory/. 2024.
Kaye P., Laflamme R., and Mosca M. An Introduction to Quantum Computing. N.Y.: Oxford University Press, 2007. 274 p.
Nielsen M. A. and Chuang I. L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2010. 676 p.
Ceselli A. and Premoli M. On good encodings for quantum annealer and digital optimization solvers // Sci. Rep. 2023. V. 13. Article No. 5628.
Koch D., Cutugno M., Patel S., et al. Variational amplitude amplification for solving QUBO problems // Quantum Rep. 2023. V.5. No.4. P.625-658.
Pokharel B., Izquierdo Z. G., Lott P. A., et al. Inter-generational comparison of quantum annealers in solving hard scheduling problems // Quantum Inf. Process. 2023. V. 22. Article No. 364.
Aggarwal D., Bennett H., Brakerski Z., et al. Lattice problems beyond polynomial time // Proc. STOC’2023. Orlando, FL, USA, 2023. P. 1516-1526.
Pass R., Tseng W.L.D., and Venkitasubramaniam M. Towards non-black-box lower bounds in cryptography // LNCS. 2011. V.6597. P.579-596.
Spakowski H., Thakur M., and Tripathi R. Quantum and classical complexity classes: Separations, collapses, and closure properties // Inform.Comput. 2005. V. 200. No. 1. P. 1-34.
Adleman L., DeMarrais J., and Huang M. Quantum computability // SIAM J.Computing. 1997. V. 26. No. 5. P.1524-1540.
Bernstein E. and Vazirani U. Quantum complexity theory // SIAM J.Computing. 1997. V. 26. No. 5. P.1411-1473.
Shor P. W. Algorithms for quantum computation: discrete logarithms and factoring // Proc. 35th Ann. Svmp. FOCS. Santa Fe, USA, 1994. P. 124-134.
Aaronson S. Quantum computing, postselection, and probabilistic polynomial-time // Proc. R. Soc. A. 2005. V. 461. P. 3473-3482.
Ogiwara M. and Hemachandra L. A. A complexity theory for feasible closure properties // J.Computer System Sci. 1993. Y. 16. No. 3. P.295-325.
Gill J.Computational complexity of probabilistic Turing machines // SIAM J.Computing. 1977. V.6. No.4. P.675-695.
Akmal S. and Williams R. MAJORITY-3SAT (and related problems) in polynomial time // Proc. 62nd Ann. Svmp. FOCS. Denver, USA, 2022. P. 1033-1043.
Bailey D. D., Dalmau V., and Kolaitis P. G. Phase transitions of PP-complete satisfiability problems // Discrete Appl. Math. 2007. V. 155. No. 12. P. 1627-1639.
Chandra S. S., Kannan R. J., Balaji B. S., et al. Efficient design and analysis of secure CMOS logic through logic encryption // Sci. Rep. 2023. V. 13. Article No. 1145.
Liang J., Wang K., Xi W., et al. SILL: Preventing structural attack for logic locking // IEICE Electronics Express. 2023. V.20. No. 2. P. 1-6.
Rajendran J. and Garg S. Logic encryption // Forte D., Bhunia S., and Tehranipoor M. M. (eds.). Hardware Protection through Obfuscation. Cham: Springer, 2017. P.71-88.
Curticapean R. The simple, little and slow things count: On parameterized counting complexity. Dissertation for Obtaining the Title of Doctor rerum naturalium (Dr. rer. nat) of the Faculties of Natural Sciences and Technology of Saarland University, Saarbriicken, 2015.
Bakali E., Chalki A., Kanellopoulos S., et al. On the Power of Counting the Total Number of Computation Paths of NPTMs. https://arxiv.org/abs/2306.11614. 2024.
О проблеме декодирования по принципу максимального правдоподобия | Прикладная дискретная математика. 2025. № 70. DOI: 10.17223/20710410/70/1
Скачать полнотекстовую версию
Загружен, раз: 28