Hazard-free Boolean circuits can be exponentially more expensive — and NP-hard to build
thomasahle · x · 2026-11-10
Engineer thomasahle posted a thread on hazards in Boolean circuits: using three-valued Kleene logic (bits are 0, 1, or u for unknown/unstable), a circuit is "hazard-free" only if it outputs the same value for bi=u as for bi=0 and bi=1.
The catch: standard constructions have hazards — MUX(x,y,s)=(x&s)|(y&¬s) outputs u at MUX(1,1,u) instead of 1, so "u" stops acting as "unknown". Fixing this takes extra gates (e.g. (x&y)|((x&s)|(y&¬s))), and hazard-free circuits can be exponentially more expensive: the cited theorem shows that if circuits deciding jn-CLIQUE require n^Ω(jn) size, then some poly-size function has hazard-free circuits requiring 2^Ω(kn) gates; constructing hazard-free Boolean circuits is NP-hard.
Related event: Building Hazard-Free Boolean Circuits Proved NP-Hard(2 posts)→
More from Research
- Your ML Model Does Not Understand Dates: Cheap Timestamp Transforms That Boost Accuracy — dima806_dima · 2026-11-10
- WorkflowArena: First Benchmark for Multi-Agent Workflow Orchestration With 145 Real-World Tasks — _akhaliq · 2026-11-10
- Kenneth Stanley's team releases open-endedness research agenda: blog + 4 preprints — kenneth0stanley · 2026-11-10
- Cellpose-SAM hits 0.163 error rate, beating human annotator disagreement on cell segmentation — RichardsonDx · 2026-11-10
- NVIDIA-led study: unblocking VLM gradients in VLA training lifts manipulation progress from 10.3% to 32.9% — stepjamUK · 2026-11-10
- Hugging Face explains Decision Models: probability outputs without text generation — ariG23498 · 2026-11-10