2 papers
cs.CC2012
Relativizing Small Complexity Classes and their Theories
Klaus Aehlig, Stephen Cook, Phuong Nguyen
Existing definitions of the relativizations of \NCOne, Ł and \NL\ do not preserve the inclusions $\NCOne \subseteq Ł$, $\NL\subseteq \ACOne$. We start by giving the first definitio…
cs.LO2010
The Complexity of Proving the Discrete Jordan Curve Theorem
Phuong Nguyen, Stephen Cook
The Jordan Curve Theorem (JCT) states that a simple closed curve divides the plane into exactly two connected regions. We formalize and prove the theorem in the context of grid gra…