I have lately been enjoying Richeson's Tales of Impossibility (see MAA review), an accessible book on the famous problems of Euclidean geometry including angle trisection/cube doubling/heptagon construction/etc. Richeson traces the history of these problems in antiquity through the middle ages and the 19th century and beyond, with many tangents/chapters on tools and methods above and beyond those afforded by Euclid.
Richeson shows how adding techniques to the geometer's toolkit often, but not always, affects the nature of the problems that she can solve. For example one of the first theorems of the Elements is a reduction showing that a ruler along with a collapsing compass is just as powerful as a ruler and a lockable compass. We also have the Renaissance result of Ferrari showing that a straightedge and a rusty compass can prove all of the first six books of Euclid. But empowering our geometer to use a neusis or a carpenter's square enables her to trisect an angle.
I'm also noticing a rough analogy between the class of problems in plane geometry that one can solve with a given set of tools and the class of problems in computational complexity one can solve with a given set of resources. Indeed much as one can create a Hasse-diagram based on the Complexity Zoo I suspect one could create a similar Venn-diagram for all the methods considered by Richeson.
But can this analogy be taken further? For example much as computational complexity theory has given us the language of hardness and completeness for certain classes of problems, would it make sense to speak of a "neusis-complete" problem?
Is there a problem solvable or a curve constructible with a compass, straightedge, and neusis such that any other problem constructible with the above is in some sense reducible thereto? Similarly are there "origami-complete" constructions?
