A polynomial-time heuristic for Circuit-SAT

Simple item page
dc.creatorCapasso, Francesco
dc.date2005-11-18
dc.date2005-11-28
dc.date.accessioned2026-07-07T06:49:37Z
dc.date.available2026-07-07T06:49:37Z
dc.descriptionIn this paper is presented an heuristic that, in polynomial time and space in the input dimension, determines if a circuit describes a tautology or a contradiction. If the circuit is neither a tautology nor a contradiction, then the heuristic finds an assignment to the circuit inputs such that the circuit is satisfied.
dc.description20 pages, 8 figures
dc.identifierhttps://arxiv.org/abs/cs/0511071
dc.identifierhttp://arxiv.org/abs/cs/0511071
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/104415
dc.subjectComputational Complexity
dc.subjectData Structures and Algorithms
dc.titleA polynomial-time heuristic for Circuit-SAT
dc.typetext

Files

Collections

arXiv