Department of Computer Science | Institute of Theoretical Computer Science

Given a Boolean Circuit with n inputs and n outputs, we want to decide
if it represents a Unique Sink Orientation (USO). USOs are useful
combinatorial objects that serve as abstraction of many relevant
optimization problems. We prove that recognizing a USO is
coNP-complete. However, the situation appears to be more complicated
for recognizing acyclic USOs. Firstly, we give a construction to prove
that there exist cyclic USOs where the smallest cycle is of
superpolynomial size. This implies that the straightforward
representation of a cycle (i.e. by a list of vertices) does not make
up for a coNP certificate. Inspired by this fact, we investigate the
connection of recognizing an acyclic USO to PSPACE and we prove that
the problem is PSPACE-complete.