17 citations · 17 across the 3 of their papers we have counts for
Showing cs.LOShow all
2 papers · 1 filter
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…