2024/01/26 by Arturo Merino, Merino, Arturo, Namrata Namrata +3
Computer Science · Engineering · #Coding theory and cryptography #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2401.14963
openalex publication_date 2024/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Can a list of binary strings be ordered so that consecutive strings differ in a single bit? Can a list of permutations be ordered so that consecutive permutations differ by a swap? Can a list of non-crossing set partitions be ordered so that consecutive partitions differ by refinement? These are examples of Gray coding problems: Can a list of combinatorial objects (of a particular type and size) be ordered so that consecutive objects differ by a flip (of a particular type)? For example, 000, 001, 010, 100 is a no instance of the first question, while 1234, 1324, 1243 is a yes instance of the second question due to the order 1243, 1234, 1324. We prove that a variety of Gray coding problems are NP-complete using a new tool we call a Gray code reduction.