Tuesday, February 02, 2016

[ntjmkgvp] Compass straightedge complexity

What is the computational complexity of questions about a compass and straightedge construction?  For example, that three or more lines/arcs intersect at a single point, or that two lines are parallel?

Involves answering questions about expressions involving square roots.

Prove that (say) a regular 17-gon construction is correct.

No comments :