17 citations · 17 across the 3 of their papers we have counts for
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★ 17 cited
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…