Pith. sign in

REVIEW 3 minor 34 references

This paper proves that the CNOT-Distance decision problem—can a given linear map on labelled wires be implemented with at most K CNOT gates—is NP-complete even under all-to-all connectivity, by reducing from Minimum Vertex Cover and showing

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

CNOT-Distance, deciding whether a given invertible binary matrix can be implemented with at most K CNOT gates under all-to-all connectivity, is NP-complete.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection A real and nontrivial result: exact CNOT minimization under all-to-all connectivity is NP-complete, and the exact distance formula for the constructed family is the key new ingredient.

arxiv 2608.03825 v1 pith:3RLYC64E submitted 2026-08-04 quant-ph cs.CC

CNOT-Distance is NP-complete under all-to-all connectivity

Antonio Acuaviva , Arturo Acuaviva , Pablo Acuaviva This is my paper
classification quant-ph cs.CC MSC 68Q1768Q2581P68 PACS 03.67.Lx
keywords CNOT circuitslinear reversible circuitsNP-completenessquantum circuit synthesisvertex coverXOR complexityapproximation hardnessall-to-all connectivity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper resolves a basic question in quantum circuit synthesis: given an invertible linear transformation on N labelled wires, can we decide whether K CNOT gates suffice when every ordered pair of wires can serve as control and target? It proves this decision problem is NP-complete. The proof constructs, from any graph G, a sparse upper-unitriangular matrix A_G whose minimal CNOT count is exactly 2|V|+2|E|+τ(G), where τ(G) is the minimum vertex-cover size. Thus the graph's combinatorial difficulty is baked directly into the circuit-minimization problem. As a result, exact CNOT-count minimisation is NP-hard to compute, NP-hard to approximate within any fixed additive constant, and the associated optimisation problem is APX-hard. This matters because it shows the hardness persists even in the most permissive connectivity model: no routing constraint or gate-availability restriction explains the difficulty.

Core claim

For every finite simple graph G, the constructed matrix A_G satisfies ℓ_CNOT(A_G) = 2|V|+2|E|+τ(G). The lower bound is obtained by unfolding an arbitrary CNOT circuit into an XOR directed acyclic graph, projecting private wire inputs to zero, and contracting nodes whose projected values coincide with earlier values; this deletes exactly 2|V|+|E| internal nodes and leaves an XOR straight-line program for the family F_G = {z+x_u+x_v : {u,v}∈E}. By the binary z-expression lemma, the XOR complexity of F_G is |E|+τ(G). Consequently CNOT-Distance is NP-complete, with hardness holding even for upper-unitriangular matrices with row Hamming weight at most four, (A−I_N)^3=0, exact order four, and budg

What carries the argument

The central object is the projection–contraction lemma, which lets one delete internal nodes of an unfolded CNOT circuit when their projected value matches an earlier available value, preserving all designated outputs. It is coupled with the Boyar–Matthews–Peralta z-expression lemma (proved self-contained in the appendix), which gives xor(F_G)=|E|+τ(G) and, more strongly, a polynomial-time extraction of a vertex cover from any straight-line program computing F_G. The constructed matrix A_G is a block upper-unitriangular matrix whose edge rows encode the parities z+x_u+x_v, turning vertex cover size into a clean additive term in the CNOT count.

Load-bearing premise

The entire lower bound rests on the claim that from any CNOT circuit for A_G one can delete exactly 2|V|+|E| internal nodes by projection and contraction while preserving all retained edge outputs; if such a deletion ever destroyed the only path that computes a remaining edge parity, the bound would collapse.

What would settle it

Pick a concrete graph, say the triangle K3 (n=3, m=3, τ=2), construct A_G on N=10 wires, and exhaustively search all CNOT circuits of length up to 13; any circuit implementing A_G would disprove ℓ_CNOT(A_G)=14. Alternatively, run the robust-extraction procedure of Lemma 3.5 on a hand-built circuit and check whether each edge output z+x_u+x_v remains computable after deleting the 2|V|+|E| nodes; a failure case directly falsifies Lemma 3.5.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Exact computation of ℓ_CNOT(A) is NP-hard even for matrices that are sparse, upper-unitriangular, satisfy (A−I_N)^3=0, and have exact order four.
  • No polynomial-time algorithm can approximate the minimum CNOT count within any fixed additive constant unless P=NP; the CNOT-circuit optimisation problem is APX-hard under L-reductions.
  • For the constructed family, any number of clean or borrowed ancillary wires that must be restored leaves the optimum unchanged, so ancillary-wire tricks cannot bypass the hardness.
  • The hardness transfers to any architecture family that contains an explicit complete bidirected subgraph on the required number of wires, including the general topology-input model.
  • A polynomial-time decoder converts any CNOT implementation of A_G into a vertex cover of G of size at most the circuit length minus 2|V|−2|E|, which is the engine behind the approximation-hardness results.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The projection–contraction technique is architectural in nature rather than specific to CNOT gates; it could plausibly extend to other reversible gate sets that compute linear forms, provided the target family admits a z-expression lemma analogous to the one used here.
  • Because the hard instances have row weight at most four and O(N) nonzero entries, the practical takeaway is that exact CNOT minimisation is likely infeasible in general; heuristics that work on typical instances cannot be backed by polynomial-time optimality certificates unless P=NP.
  • The exact formula ℓ_CNOT(A_G)=2|V|+2|E|+τ(G) gives algorithm designers a concrete stress-test family: any synthesis heuristic claiming near-optimal performance on sparse upper-triangular matrices can be checked against this family, where the true optimum is as hard to compute as vertex cover.
  • The paper's hardness is worst-case; it does not imply that typical or average instances are hard, and the conclusion explicitly notes that no statement about typical instances follows.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper proves that the decision problem CNOT-Distance is NP-complete in the fixed-label, all-to-all connectivity model. The reduction is from Vertex Cover: to each finite simple graph G=(V,E) it assigns a sparse upper-unitriangular matrix A_G of dimension 2|V|+|E|+1 satisfying (A_G-I)^3=0 and having order exactly four, and proves the exact identity ℓ_CNOT(A_G)=2|V|+2|E|+τ(G). The upper bound is an explicit circuit built from any vertex cover. The lower bound unfolds an arbitrary CNOT circuit into an XOR DAG and, through the projection-contraction Lemma 3.5, deletes 2|V|+|E| forced internal nodes while preserving all designated outputs; the remaining DAG is normalized to an XOR straight-line program for the z-expression family F_G. A self-contained proof of the Boyar-Matthews-Peralta lemma (Appendix A) gives xor(F_G)=|E|+τ(G), completing the exact-distance formula. The same extraction provides a polynomial-time decoder from any implementation to a vertex cover, and the paper derives NP-hardness of exact computation, NP-hardness of approximation within every fixed additive constant, and APX-hardness of the CNOT minimisation problem via an L-reduction from cubic Vertex Cover. It also shows that on the constructed family the optimum is unchanged by any finite number of clean or borrowed ancillas that must be restored.

Significance. If correct, this settles a basic open problem: CNOT-count minimisation is hard even when every control-target pair is available, so the hardness is inherent to linear-reversible synthesis rather than to routing constraints. The main technical achievement is the lower-bound extraction, which is genuinely robust: it handles arbitrary cancellations and unbounded reuse of parities, and it does not impose a cancellation-free normal form. The paper strengthens this with a polynomial-time decoder, giving tight additive-inapproximability and APX-hardness, and with ancilla-robustness for the reduction family. The proof of the auxiliary XOR-complexity lemma is included in full, making the argument verifiable without relying on an opaque citation. The authors are explicit in Section 5 that the results are worst-case and that the ancilla-robustness equality is specific to the constructed family; these caveats are accurate and do not affect the main theorem. I checked the potential failure mode in Lemma 3.5—whether deleting the earliest edge-variable node could destroy a retained edge output—and the induction in Lemma 2.2 does rule it out; I found no load-bearing gap.

minor comments (3)
  1. [Section 3B, Lemma 3.5] The claim that the 2n displayed vertex-output forms are pairwise distinct before projection is correct but very compressed. Spelling out the coefficient comparison (e.g., the q_v-coefficient distinguishes e^a_v from forms with w≠v; the z-coefficient distinguishes e^a_v from e^b_v) would make this key counting step easier to verify.
  2. [Section 3B, Lemma 3.5] In the private-edge stage, the sentence 'the source y_e is the only earlier node with a nonzero y_e coefficient' carries the whole argument. I suggest expanding it: an earlier internal node with nonzero y_e would contradict 'earliest', and if both parent slots were the source y_e the node value would be zero.
  3. [General] A few typographical artifacts need cleaning up in the final version (for example, '2ndisplayed' in Lemma 3.5 appears to be '2n displayed').

Circularity Check

0 steps flagged

No significant circularity: the exact-distance reduction is self-contained and does not reduce to its inputs.

full rationale

The central derivation is the exact identity l_CNOT(A_G)=2|V|+2|E|+tau(G) (Theorem 3.2). The upper bound (Lemma 3.3) is an explicit circuit constructed from a vertex cover, and the lower bound (Lemmas 3.5 and 3.6) unfolds an arbitrary CNOT circuit into an XOR DAG, applies projection–contraction to delete 2|V|+|E| forced nodes, and then invokes Lemma 2.1 to lower-bound the remaining XOR straight-line program for F_G by |E|+tau(G). Lemma 2.1 is not assumed as an unverified black box: Appendix A gives a self-contained proof over F2 with an explicit polynomial-time vertex-cover extraction, independent of any fitted quantity or of the CNOT optimisation problem. No parameter of the reduction is calibrated to the desired answer; the target matrices A_G are constructed directly from the graph, and no quantity in the lower bound is defined in terms of l_CNOT(A_G) or of the problem being proved hard. The proof does not rely on a self-citation chain: the external citations [20,22,23] are standard NP- and APX-completeness results that do not presuppose CNOT distance, and the Boyar–Matthews–Peralta lemma is re-proved within the paper. The structural restrictions and ancillary-wire robustness (Proposition 3.8) follow from the same explicit accounting rather than from an imported uniqueness theorem or an ansatz smuggled in by citation. The residual risk noted in the text is the absence of a machine-checked formalisation of a complex combinatorial argument; that is a correctness risk, not a circularity. No circular step is exhibited.

Axiom & Free-Parameter Ledger

0 free parameters · 7 axioms · 0 invented entities

There are no fitted constants or ad hoc parameters: the graph G is the input, and tau(G) is a computed quantity. The paper introduces no new physical entities. It relies on standard complexity-theoretic results (Vertex Cover NP-completeness, cubic APX-completeness, L-reductions) and on a kernel lemma that is proved self-contained in Appendix A. The domain assumptions are the definition of the all-to-all CNOT distance and the clean/borrowed ancillary models.

axioms (7)
  • standard math GL(N,2) is generated by the coordinate transvections T_ij=I_N+E_ij; CNOT count is the Cayley graph distance in Cay(GL(N,2), Sigma_N).
    Section 2A defines the distance and uses this generation as the foundation; elementary linear algebra.
  • standard math Vertex Cover is NP-complete.
    Cited [20] (Karp) and used as the source problem in Theorem 1.1.
  • standard math Minimum Vertex Cover on cubic graphs is APX-complete.
    Cited [22] (Alimonti and Kann) and used in Corollary 4.4.
  • standard math The L-reduction framework of Papadimitriou and Yannakakis preserves APX-hardness.
    Cited [23] and used to define the L-reduction in Corollary 4.4.
  • domain assumption All-to-all connectivity means every ordered pair of distinct wires admits a CNOT gate with no routing constraints.
    Section 2 defines the problem model; this is the premise whose removal would change the metric.
  • domain assumption Clean and borrowed ancilla models require the ancilla wires to be restored exactly; borrowed implementations become clean when ancilla inputs are fixed to zero.
    Section 2B defines these models; used in Proposition 3.8.
  • standard math Every invertible matrix has a CNOT implementation of length at most N^2+2N via Gaussian elimination.
    Used in the NP-membership proofs in Section 4A; argued in the text.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of CNOT-Distance is NP-complete under all-to-all connectivity." pith.science (2026). https://pith.science/paper/3RLYC64E

@misc{pith2026260803825,
  author       = {Pith},
  title        = {Pith review of: CNOT-Distance is NP-complete under all-to-all connectivity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3RLYC64E}},
  note         = {Machine review of arXiv:2608.03825}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Given $A\in\operatorname{GL}(N,2)$ and an integer $K$, we ask whether $A$ can be implemented by at most $K$ CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph $G=(V,E)$, we construct an upper-unitriangular matrix $A_G\in\operatorname{GL}(2|V|+|E|+1,2)$ satisfying $\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+\tau(G)$, where $\tau(G)$ is the minimum vertex-cover size. Each target matrix has $O(N)$ nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 30 canonical work pages · 4 internal anchors

  1. [1]

    CNOT-Distance is NP-complete under all-to-all connectivity

    INTRODUCTION Controlled-NOT (CNOT) gates are a central primi- tive in quantum-circuit synthesis. Together with arbi- trary one-qubit gates, they form a universal gate library [1]. Circuits composed exclusively of CNOT gates imple- ment precisely the invertible linear transformations over F2. Such linear-reversible transformations arise both as stand-alone...

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  2. [2]

    every row ofAhas Hamming weight at most four andAhasO(N)nonzero entries; 3.(A−I N )3 = 0andAhas exact order four; and 4.K <2N. A. Proof strategy and organisation Our reduction is fromVertex Cover, which is NP- complete [20]. Given a finite simple graphG= (V, E), we construct in polynomial time an upper-unitriangular matrix AG ∈GL(2|V|+|E|+ 1,2) and prove ...

    work page

  3. [3]

    , N}and denote byIN theN×N identity matrix

    NOT A TION AND PRELIMINAR Y RESUL TS We write [N] ={1, . . . , N}and denote byIN theN×N identity matrix. Fori, j∈[N], we denote byE ij the N×Nmatrix unit whose (i, j)-entry is 1 and whose remaining entries are 0. We identify the values on theN wires with a column vectorx= (x 1, . . . , xN )T ∈F N 2 . For distincti, j∈[N], the operation xi ←x i +x j has co...

    work page

  4. [4]

    LetG= (V, E) be a finite simple graph, and write n=|V|, m=|E|

    THE REDUCTION The reduction separates a graph-independent synthesis cost from the graph-dependent termτ(G), the size of a minimum vertex cover. LetG= (V, E) be a finite simple graph, and write n=|V|, m=|E|. We construct a transformation on N= 2n+m+ 1 labelled data wires. There is a distinguished wirez, two wiresq v, xv for eachv∈V, and one wirey e for eac...

    work page

  5. [5]

    We first prove the decision result and its ancillary vari- ants, and then derive hardness for exact computation, fixed-additive approximation, and multiplicative approx- imation

    COMPLEXITY CONSEQUENCES The exact-distance identity transfers several complex- ity properties ofVertex Coverto CNOT synthesis. We first prove the decision result and its ancillary vari- ants, and then derive hardness for exact computation, fixed-additive approximation, and multiplicative approx- imation. A. Decision and exact computation We begin with the...

    work page

  6. [6]

    Thus ex- act CNOT-count minimisation remains computation- ally hard even after routing constraints and restricted gate availability are removed

    CONCLUSION We have proved thatCNOT-Distanceis NP- complete in the fixed-label, all-to-all model. Thus ex- act CNOT-count minimisation remains computation- ally hard even after routing constraints and restricted gate availability are removed. Hardness already holds for sparse upper-unitriangular targets whose rows have Hamming weight at most four, for whic...

    work page

  7. [7]

    The image of every input variable and every value wi withi≤tis either zero or one element ofB t

    work page

  8. [8]

    Every auxiliary-line valuew i withi≤thas image zero

    work page

  9. [9]

    Every element ofB t is the image of at least one input variable

    work page

  10. [10]

    Fort= 0, takeQ 0 =L, letρ 0 be the identity map, and take the input variables inU G as the basisB 0

    We have dimQ t ≥ |V|+ 1−a t. Fort= 0, takeQ 0 =L, letρ 0 be the identity map, and take the input variables inU G as the basisB 0. All four properties then hold. Suppose that the properties hold after linet−1. First assume that linetis auxiliary. By the first property, each ofρ t−1(pt) andρ t−1(qt) is either zero or an element of Bt−1. Define Qt =Q t−1 ρt−...

    work page

  11. [11]

    Elementary gates for quantum compu- tation,

    A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary gates for quantum compu- tation,”Physical Review A, vol. 52, pp. 3457–3467, Nov. 1995

    work page 1995

  12. [12]

    Improved simulation of stabilizer circuits,

    S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits,”Physical Review A, vol. 70, p. 052328, Nov. 2004

    work page 2004

  13. [13]

    On the controlled-NOT complexity of controlled-NOT–phase circuits,

    M. Amy, P. Azimzadeh, and M. Mosca, “On the controlled-NOT complexity of controlled-NOT–phase circuits,”Quantum Science and Technology, vol. 4, no. 1, 14 p. 015002, 2018

    work page 2018

  14. [14]

    Clifford circuit optimization with templates and symbolic pauli gates,

    S. Bravyi, R. Shaydulin, S. Hu, and D. Maslov, “Clifford circuit optimization with templates and symbolic pauli gates,”Quantum, vol. 5, p. 580, Nov. 2021

    work page 2021

  15. [15]

    Global synthesis of CNOT circuits with holes,

    E. Murphy and A. Kissinger, “Global synthesis of CNOT circuits with holes,” inProceedings of the 20th Interna- tional Conference on Quantum Physics and Logic (QPL 2023)(S. Mansfield, B. Valiron, and V. Zamdzhiev, eds.), vol. 384 ofElectronic Proceedings in Theoretical Com- puter Science, pp. 75–88, Open Publishing Association, 2023

    work page 2023

  16. [16]

    Optimal synthesis of linear reversible circuits,

    K. N. Patel, I. L. Markov, and J. P. Hayes, “Optimal synthesis of linear reversible circuits,”Quantum Infor- mation and Computation, vol. 8, no. 3–4, pp. 282–294,

    work page

  17. [17]

    Optimising quantum circuits is generally hard

    J. van de Wetering and M. Amy, “Optimising quantum circuits is generally hard.” arXiv:2310.05958v3 [quant- ph], 2024. doi:10.48550/arXiv.2310.05958

    Pith/arXiv arXiv doi:10.48550/arxiv.2310.05958 2024

  18. [18]

    Quantum circuits of CNOT gates: opti- mization and entanglement,

    M. Bataille, “Quantum circuits of CNOT gates: opti- mization and entanglement,”Quantum Information Pro- cessing, vol. 21, p. 269, 2022

    work page 2022

  19. [19]

    On exact sizes of minimal CNOT circuits,

    J. E. Christensen, S. F. Jørgensen, A. Pavlogiannis, and J. van de Pol, “On exact sizes of minimal CNOT circuits,” inReversible Computation(R. Gl¨ uck and R. Kaarsgaard, eds.), vol. 15716 ofLecture Notes in Computer Science, pp. 71–88, Cham: Springer, 2025. doi:10.1007/978-3-031-97063-4 6

    doi:10.1007/978-3-031-97063-4 2025

  20. [20]

    Minimum synthesis cost of CNOT circuits,

    A. Bu, E. Fan, and R. Joo, “Minimum synthesis cost of CNOT circuits,”Quantum Information Processing, vol. 24, p. 208, July 2025

    work page 2025

  21. [21]

    Lower bounds for the CNOT-complexity of linear reversible operators

    S. F. Jørgensen, “Lower bounds for the CNOT- complexity of linear reversible operators,” 2026. arXiv:2607.22248

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  22. [22]

    Explicit matrices overZ 2 with CNOT and row complexity 4n−o(n) and local logic gates,

    S. Gong and A. Yu, “Explicit matrices overZ 2 with CNOT and row complexity 4n−o(n) and local logic gates,” 2026

    work page 2026

  23. [23]

    Gaussian elimination ver- sus greedy methods for the synthesis of linear reversible circuits,

    T. Goubault de Brugi` ere, M. Baboulin, B. Valiron, S. Martiel, and C. Allouche, “Gaussian elimination ver- sus greedy methods for the synthesis of linear reversible circuits,”ACM Transactions on Quantum Computing, vol. 2, no. 3, pp. 11:1–11:26, 2021

    work page 2021

  24. [24]

    CNOT minimal circuit synthesis: A reinforcement learning approach,

    R. Romanello, D. Lizzio Bosco, J. Cossio, D. Sutulovic, G. Serra, C. Piazza, and P. Burelli, “CNOT minimal circuit synthesis: A reinforcement learning approach,” in2025 IEEE International Conference on Quantum Artificial Intelligence (QAI), pp. 253–260, IEEE, 2025. doi:10.1109/QAI63978.2025.00047

    arXiv 2025

  25. [25]

    AlphaCNOT: Learning CNOT minimization with model-based planning,

    J. Cossio, D. Lizzio Bosco, R. Romanello, G. Serra, and C. Piazza, “AlphaCNOT: Learning CNOT minimization with model-based planning,” 2026

    work page 2026

  26. [26]

    Parallelizable Exact Synthesis of Quantum Circuits via Semi-Tensor Product

    C. Li, D. Gao, X. Zhou, J. Guan, P. Zhu, and Z. Chu, “Parallelizable exact synthesis of quantum circuits via semi-tensor product,” 2026. arXiv:2607.24195

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  27. [27]

    Toward Minimum Graphic Parity Networks

    Y. Cao, Y. Lu, J. Nie, X. Sun, and G. Tian, “To- ward minimum graphic parity networks.” arXiv preprint arXiv:2509.10070, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  28. [29]

    Optimal space–depth trade-off of CNOT cir- cuits in quantum logic synthesis,

    J. Jiang, X. Sun, S.-H. Teng, B. Wu, K. Wu, and J. Zhang, “Optimal space–depth trade-off of CNOT cir- cuits in quantum logic synthesis,” inProceedings of the Fourteenth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 213–229, Society for Industrial and Applied Mathematics, 2020

    work page 2020

  29. [30]

    CNOT-optimal circuit synthesis,

    Y. Kang, “CNOT-optimal circuit synthesis,” tech. rep., Research Science Institute, Massachusetts Institute of Technology, 2023. available online

    work page 2023

  30. [31]

    Reducibility among combinatorial prob- lems,

    R. M. Karp, “Reducibility among combinatorial prob- lems,” inComplexity of Computer Computations (R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, eds.), pp. 85–103, New York: Plenum Press, 1972. doi:10.1007/978-1-4684-2001-2 9

    doi:10.1007/978-1-4684-2001-2 1972

  31. [32]

    Logic minimiza- tion techniques with applications to cryptology,

    J. Boyar, P. Matthews, and R. Peralta, “Logic minimiza- tion techniques with applications to cryptology,”Jour- nal of Cryptology, vol. 26, no. 2, pp. 280–312, 2013. doi:10.1007/s00145-012-9124-7

    work page doi:10.1007/s00145-012-9124-7 2013

  32. [33]

    Some APX-completeness re- sults for cubic graphs,

    P. Alimonti and V. Kann, “Some APX-completeness re- sults for cubic graphs,”Theoretical Computer Science, vol. 237, no. 1–2, pp. 123–134, 2000

    work page 2000

  33. [34]

    Optimization, approximation, and complexity classes,

    C. H. Papadimitriou and M. Yannakakis, “Optimization, approximation, and complexity classes,”Journal of Com- puter and System Sciences, vol. 43, no. 3, pp. 425–440, 1991

    work page 1991

  34. [2008]

    doi:10.26421/QIC8.3-4-4

    work page doi:10.26421/qic8.3-4-4

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.