3 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…
cs.LO2005
Theories for TC0 and Other Small Complexity Classes
Phuong Nguyen, Stephen Cook
We present a general method for introducing finitely axiomatizable "minimal" two-sorted theories for various subclasses of P (problems solvable in polynomial time). The two sorts a…