Boolean satisfiability (SAT) is an important NP-hard problem.
Traditional attempts to improve the performance of solving SAT problems use sophisticated search techniques in serial processors.
FPGA-based approaches implement a custom configured MIMD to evaluate all direct transitive implications in a single cycle.
Although promising, custom placement and routing is NP-hard.
Previous results present no proof of an upper bound on P&R compilation time or routability of classes of SAT problems.