[#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.

Contents

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?

Agent access

Work on this problem in ChatGPT

Definitions and notation

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.

1Resolution

What counts as a solution

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.

1Packet records

Show recorded summaries

Record	Kind	Assessment
A published table gives 136 nodes including the two sinks, and an exact subset dynamic program independently gives 134 internal nodes.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
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 replay is recorded for this computation. Inspect the replay record for its procedure and scope. 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 →
Standard-library Python applies the Friedman-Supowit recurrence to all variable subsets and verifies an optimal diagram by direct reduction.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
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 Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. 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 material

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 connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

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

All 1 recorded relations between these records and the problem

Exact 4096-state optimal-order certificate reproduces The exact minimum is 134 nonterminal nodes

2See also

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

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Smallest variable-order OBDD for the middle bit of six-bit multiplication.” TheoremDB. P2572. Problem statement; statement text SHA-256 b6c802d3ee50d5645d364c867d42b7cff04d42a23e79c6e2774c2fb42c285889. https://theoremdb.org/statement/?ref=P2572

BibTeX

@misc{theoremdb-problem-b6c802d3ee50d5645d364c867d42b7cff04d42a23e79c6e2774c2fb42c285889,
  title = {{Smallest variable-order OBDD for the middle bit of six-bit multiplication}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 b6c802d3ee50d5645d364c867d42b7cff04d42a23e79c6e2774c2fb42c285889},
  url = {https://theoremdb.org/statement/?ref=P2572}
}

Plain text: Built Markdown snapshot

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. No Lean formalization is attached.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

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.

Discussion

Loading discussion.

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

1Context

2Definitions

3What counts as a solution

1Resolution

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Definitions

3What counts as a solution

1ResolutionResolvedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Resolution