First pair the $$$128$$$ bits into $$$64$$$ pairs and calculate the OR of each pair. If there is an anomaly, at least $$$2$$$ pairs will have an OR of $$$1$$$.
Construct a tripartite graph, where the three parts have sizes $$$4$$$, $$$5$$$ and $$$5$$$ respectively. Call the parts $$$A$$$, $$$B$$$, $$$C$$$. This graph has a total of $$$4 \times 5 + 4 \times 5 + 5 \times 5 = 65$$$ edges. Assign each bit to one of these edges, so there is $$$1$$$ unused edge.
For each vertex, calculate the OR of all edges that include it. Define a vertex to be active if this OR is equal to $$$1$$$. Then, we either have:
- All three parts have active nodes, or
- There exists a part with two active nodes
if and only if there is an anomaly.
Given a part with $$$X$$$ nodes, we can check both:
- whether it has an active node
- whether it has $$$\geq 2$$$ active nodes
using $$$3X - 4$$$ operations as follows. Suppose the nodes are $$$A_1, A_2, \cdots, A_X$$$.
Calculate $$$P_i = A_1 \bigvee A_2 \bigvee \cdots \bigvee A_i$$$. This can be done by letting $$$P_1 = A_1$$$ and $$$P_i = P_{i-1} \bigvee A_i$$$. Note $$$P_X$$$ is $$$1$$$ if and only if there is at least one active node.
Calculate $$$P_i \bigwedge A_{i+1}$$$ for each $$$1 \leq i \lt X$$$. Note that if the component has at least two active nodes, $$$P_i \bigwedge A_{i+1} = 1$$$ for some $$$i$$$.
Take the OR of these $$$X-1$$$ values.
Step $$$1$$$ requires $$$X-1$$$ gates, step $$$2$$$ requires $$$X-1$$$, and step $$$3$$$ requires $$$X-2$$$ gates, for a total of $$$3X - 4$$$.
Overall, we need:
- $$$64$$$ gates to compute the ORs of pairs
- $$$\sum_{\text{node } v} (\text{deg}(v) - 1) = 2 E - V = 2 \times 64 - 14 = 114$$$ gates to compute whether each node is active
- $$$3 \times |A| - 4 = 8$$$ gates to compute $$$f_A$$$, which is $$$1$$$ if $$$A$$$ has at least one active node, and $$$g_A$$$, which is $$$1$$$ if $$$A$$$ has at least two active nodes
- $$$3 \times |B| - 4 = 11$$$ and $$$3 \times |C| - 4 = 11$$$ gates to do the same for $$$B$$$ and $$$C$$$
- $$$5$$$ gates for the expression $$$g_A \bigvee g_B \bigvee g_C \bigvee (f_A \bigwedge f_B \bigwedge f_C)$$$
Which adds up to $$$64 + 114 + 8 + 11 + 11 + 5 = 213$$$ gates.
Once again, congratulations ChatGPT!
Auto comment: topic has been updated by literalchild (previous revision, new revision, compare).
ChatGPT broke the system
How did it find it? Did this need pro or was 5.5 enough? Details would be interesting.
I used the latest model (5.5) on Thinking Mode on a Plus account.
My first prompt just asked it to solve the problem. It came up with the idea of
arranging the bits in a grid.
My next prompt asked it to solve in $$$\leq 256$$$ gates. It came up with the idea of
Arranging the bits in $$$64$$$ pairs, so at least two pairs have OR equal to $$$1$$$ if there is an anomaly.
My third prompt asked it to solve using around $$$215$$$ gates. Despite the fact that the previous two ideas, when combined, gave a full solution, ChatGPT was unable to find it in $$$7$$$ minutes. I had to prompt it to explicitly merge the two ideas before it saw the full solution.
Some time later, I asked ChatGPT to solve the problem in $$$\leq 214$$$ gates (on the same chat instance), and it came up with the construction for $$$213$$$ gates.
Amazing. I wonder how much better it can do. My friends tell me that 5.4/5.5 Pro is already solving their open research problems. Did you use the web interface or codex?
I just used the web interface.
I think (not entirely sure) at the moment for these sort of individual problems where you wouldn’t need to cross codebases and files, pro on web interface is better than codex.
I think that the solution proposed by ChatGPT can be further optimized by not calculating the value P[n] (OR of the whole part), as we don't actually use it later. Thus we can lower the number of gates needed to just 210, because we use one gate less for each of the 3 parts.
It is possible for all three parts to each have exactly one active node.
Thus we need to calculate the OR of the whole part to check this condition.
Nevermind, I am stupid