[#P2572] Smallest variable-order OBDD for the middle bit of six-bit multiplication

A mathematical schematic of Smallest variable-order OBDD for the middle bit of six-bit multiplication. — A statement-only illustration of the mathematical objects and operations in this problem.

Problem. Let \(X=\sum_{i=0}^5 2^i x_i\), \(Y=\sum_{i=0}^5 2^i y_i\), and \(f(x,y)=\lfloor XY/2^5\rfloor\bmod 2\). What is the minimum number of nonterminal nodes in a reduced ordered binary decision diagram for \(f\), minimized over all \(12!\) variable orders?

1Context

The current upper bound is 140 nodes. The optimization has 479001600 raw orders, while every completed order can be independently recounted from its residual truth tables.

2Definitions

Definition 1 (A reduced OBDD merges isomorphic subgraphs and suppresses a test whose two children agree). A reduced OBDD merges isomorphic subgraphs and suppresses a test whose two children agree.

Definition 2 (The two terminal nodes). The two terminal nodes are excluded from the node count.

3What counts as a solution

Give an order and its reduced OBDD together with a certificate that every variable order needs at least as many nonterminal nodes.

1The answerReproducednot Lean-verified

Answer (The exact minimum is 134 nonterminal nodes). A published table gives 136 nodes including the two sinks, and an exact subset dynamic program independently gives 134 internal nodes.^[1]

Verification

The minimum is \[ \boxed{134} \] nonterminal nodes. One optimal variable order is \[ y_3,y_2,y_1,y_0,x_3,x_2,x_4,x_5,x_1,y_4,y_5,x_0. \] The numbers of nodes carrying those labels are \[ 1,2,4,8,13,23,31,18,20,8,4,2, \] whose sum is 134.

Amano's 2010 survey already records the exact small-width table. Its middle bit at operand width 6 is bit 5 under the candidate's zero-based convention. Figure 1 gives 136 as the minimum OBDD size at that width. Definition 1 counts every graph node, including the 0-sink and 1-sink. The middle-product function assumes both values, so both sinks occur. The convention in this candidate excludes them, giving \(136-2=134\). The same figure lists 156 total nodes for the quasi-reduced model, which keeps tests whose two children agree.

The executable certificate regenerates the truth table, evaluates every subset state in the Friedman-Supowit dynamic program, and obtains 134 across all \(12!=479{,}001{,}600\) orders. It finds 96 optimal orders. A separate bottom-up reduction builds the diagram for the displayed order and recounts its 134 nonterminal nodes.

1Records

Record	Kind	Assessment
	Result	Reproduced
claim · Computation 1 A published table gives 136 nodes including the two sinks, and an exact subset dynamic program independently gives 134 internal nodes.^[1] Relevance to this problem For Smallest variable-order OBDD for the middle bit of six-bit multiplication, record mpb6-claim-exact-minimum-134 (“The exact minimum is 134 nonterminal nodes”) records a bound, answer, status fact, or structural consequence. The record states: A published table gives 136 nodes including the two sinks, and an exact subset dynamic program independently gives 134 internal nodes. Evidence ReproducedA computation someone reran from the artifact on this page. Record state established Scope the reduced ordered binary decision diagram for bit 5 of the product of two unsigned six-bit integers, minimized over all orders of its 12 input variables and counting nonterminal nodes only Sources Reference 1 Details The minimum is \[ \boxed{134} \] nonterminal nodes. One optimal variable order is \[ y_3,y_2,y_1,y_0,x_3,x_2,x_4,x_5,x_1,y_4,y_5,x_0. \] The numbers of nodes carrying those labels are \[ 1,2,4,8,13,23,31,18,20,8,4,2, \] whose sum is 134. Amano's 2010 survey already records the exact small-width table. Its middle bit at operand width 6 is bit 5 under the candidate's zero-based convention. Figure 1 gives 136 as the minimum OBDD size at that width. Definition 1 counts every graph node, including the 0-sink and 1-sink. The middle-product function assumes both values, so both sinks occur. The convention in this candidate excludes them, giving \(136-2=134\). The same figure lists 156 total nodes for the quasi-reduced model, which keeps tests whose two children agree. The executable certificate regenerates the truth table, evaluates every subset state in the Friedman-Supowit dynamic program, and obtains 134 across all \(12!=479{,}001{,}600\) orders. It finds 96 optimal orders. A separate bottom-up reduction builds the diagram for the displayed order and recounts its 134 nonterminal nodes. Open full record →
	Artifact	Reproduced
artifact · Artifact 1 Standard-library Python applies the Friedman-Supowit recurrence to all variable subsets and verifies an optimal diagram by direct reduction.^[2] Relevance to this problem For Smallest variable-order OBDD for the middle bit of six-bit multiplication, record mpb6-artifact-subset-dp-and-obdd (“Exact 4096-state optimal-order certificate”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python applies the Friedman-Supowit recurrence to all variable subsets and verifies an optimal diagram by direct reduction. Evidence ReproducedA computation someone reran from the artifact on this page. Record state available Scope all 4096 subsets of the 12 input variables and the induced coverage of all 12-factorial variable orders for the stated six-bit middle-product function Sources Reference 2 Entry point `join source_lines with newline and run with python3` Runtime CPython 3, standard library only Details For a set \(S\) of variables already tested, let \(R_S\) be the set of distinct residual Boolean functions obtained by assigning every variable in \(S\). For \(v\notin S\), define \[ c(S,v)=\#\{g\in R_S:g\|_{v=0}\ne g\|_{v=1}\}. \] When an order has prefix set \(S\) and tests \(v\) next, its reduced OBDD has exactly \(c(S,v)\) nodes labeled \(v\). Equal residual functions merge, and a residual independent of \(v\) suppresses that test. This count depends on the set \(S\) and the next variable \(v\). The dynamic program is \[ D(\varnothing)=0,\qquad D(T)=\min_{v\in T}\bigl(D(T\setminus\{v\})+c(T\setminus\{v\},v)\bigr). \] Choosing the final variable in each prefix proves by induction that \(D(T)\) is the least node count contributed by the variables in \(T\). Thus \(D(V)\) minimizes over every complete order. The replay gets \(D(V)=134\), with 96 minimizing orders. The program stores each residual truth table as an exact Python integer. Across all 4,096 subsets it encounters 221,737 distinct residual instances. It also constructs a canonical reduced diagram for one optimal order by merging equal child pairs and suppressing equal children. The direct build has 134 nonterminal nodes. Hashes cover the truth table, the complete cost array, the dynamic-programming array, all 96 optimal orders, and the rebuilt diagram. The canonical report has SHA-256 digest `dfb779421d8f11b9661b6c040165246c83c49a286b9ccc0908fec204cf5636a1`. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. SOLVED in the reviewed TheoremDB packet as of 2026-08-01. A published table gives 136 nodes including the two sinks, and an exact subset dynamic program independently gives 134 internal nodes.

Each variable order has a unique reduced OBDD, so its node count is an exact, memoizable objective. Reversal, operand exchange, and bit symmetries should be quotiented before branching.
A lower certificate can store the best attainable residual-function partitions for each order prefix rather than all complete diagrams.
Fresh exact-title, parameter, source, and corpus searches were completed on 2026-08-01.

Recorded example 1. The order y_0,y_1,y_2,y_3,x_3,x_2,x_4,x_5,x_0,y_4,y_5,x_1 gives a 140-node reduced OBDD.

Computational notes

Exhaustive enumeration of every variable order gave exact minima 2, 6, 12, and 29 nodes for operand widths 1, 2, 3, and 4. Twenty thousand seeded orders at width 5 found 61 nodes, and twenty thousand at width 6 found the stated 140-node order; direct bottom-up reduction verified that node count.

How the 2 records connectTyped relations and evidence flow

ProblemSmallest variable-order OBDD for the middle bit of six-bit multiplication

Computation 1The exact minimum is 134 nonterminal nodesin this packetReproduced
Artifact 1Exact 4096-state optimal-order certificatereproducesReproduced

2See also

Multiplicative complexity of the six-bit threshold-at-least-three functionboolean functions
Leaf complexity of six-vertex graph connectivityboolean functions
Covering radius of the second-order Reed-Muller code RM(2,8)boolean functions

How to cite

TheoremDB contributors, “Smallest variable-order OBDD for the middle bit of six-bit multiplication,” TheoremDB research memory, snapshot of July 24, 2026. https://theoremdb.org/statements/middle-product-bit-obdd-six

This page as plain text: middle-product-bit-obdd-six.md

This problem includes 2 records joined by 1 typed links, sourced from bulletin.eatcs.org^[1], current as of July 24, 2026.

1Lean verification

Lean formalization needed

An informal proof is recorded. A Lean formalization still needs to be attached. TheoremDB Researcher can start from the exact statement and pinned world.

Open TheoremDB Researcher

The prefilled request prepares the target and checks drafts. It submits the accepted proof and polls verification through any packet-review handoff.

1References

Packet source. Kazuyuki Amano, Researching the Complexity of Boolean Functions with Computers, Bulletin of the EATCS 101 (June 2010), 64-91: Definition 1 on page 66 counts all nodes; Figure 1 and the exact dynamic-programming discussion on page 67 give minimum OBDD size 136 at operand width 6. Pages 66-67, OBDD node convention and width-six table. ↗journal article · primary source · checked 2026-08-01Source use: original summary.This is the primary or maintained source used to check the formulation, neighboring results, and current research boundary.Also cited at Kazuyuki Amano, Researching the Complexity of Boolean Functions with Computers, Bulletin of the EATCS 101 (June 2010), 64-91: Definition 1 on page 66 counts all nodes; Figure 1 and the exact dynamic-programming discussion on page 67 give minimum OBDD size 136 at operand width 6.For Smallest variable-order OBDD for the middle bit of six-bit multiplication, the reviewed source scope is Kazuyuki Amano, Researching the Complexity of Boolean Functions with Computers, Bulletin of the EATCS 101 (June 2010), 64-91: Definition 1 on page 66 counts all nodes; Figure 1 and the exact dynamic-programming discussion on page 67 give minimum OBDD size 136 at operand width 6. The packet makes no inference beyond that cited scope.Source named by the research packet.
Steven J. Friedman and Kenneth J. Supowit, Finding the Optimal Variable Ordering for Binary Decision Diagrams, 24th ACM/IEEE Design Automation Conference (1987), Section 2 lemma and Section 3 algorithm; journal version, IEEE Transactions on Computers 39(5), 710-713 (1990), DOI 10.1109/12.53586. Steven J. Friedman and Kenneth J. Supowit, Finding the Optimal Variable Ordering for Binary Decision Diagrams, 24th ACM/IEEE Design Automation Conference (1987), Section 2 lemma and Section 3 algorithm; journal version, IEEE Transactions on Computers 39(5), 710-713 (1990), DOI 10.1109/12.53586. ↗proceedings article · primary source · checked 2026-08-01Source use: original summary.For Smallest variable-order OBDD for the middle bit of six-bit multiplication: Standard-library Python applies the Friedman-Supowit recurrence to all variable subsets and verifies an optimal diagram by direct reduction.

Finite variable-order optimization with canonical reduced diagrams and exact node counts.

[#P2572] Smallest variable-order OBDD for the middle bit of six-bit multiplication

1Context

2Definitions

3What counts as a solution

1The answerReproducednot Lean-verified

1Records

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Definitions

3What counts as a solution

1The answerReproducednot Lean-verified

1Records

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance