On the complexity of detecting hazards

DOI10.1016/j.ipl.2020.105980zbMath1462.68072arXiv2006.10592OpenAlexW3033867911MaRDI QIDQ2203575

Balagopal Komarath, Nitin Saurabh

Publication date: 7 October 2020

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.10592

zbMATH Keywords

computational complexitylower boundSETHlogic hazard

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Fault detection; testing in circuits and networks (94C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Related Items (1)

Notes on Hazard-Free Circuits

Cites Work

• Unnamed Item
• On the number of prime implicants
• Which problems have strongly exponential complexity?
• Exact algorithms for maximum independent set
• A logic hazard detection and elimination method
• On the complexity of hazard-free circuits
• Hazard Detection in Combinational and Sequential Switching Circuits
• On the complexity of \(k\)-SAT

This page was built for publication: On the complexity of detecting hazards