Fold-and-cut problem in three dimensions The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include polygons"
My question

Question 1 What is the time complexity for finding such a crease pattern?
Question 2 How do we express; $\chi(P)$ ie the minimum number of  folds required to make a crease pattern from which the polygon $P$ can be cut out?
  Question 3 Does the fold-and-cut-theorem have a three dimensional analog?

Would also request for a reference to the proof.
 A: (Revised) Let me first answer your request for a reference, and then reply
to the three questions.
The most detailed proof of the One-Cut Theorem is in Chapter 17 of

Geometric Folding Algorithms: Linkages, Origami, Polyhedra.
  Cambridge. 2007. (Book link). 

Here is a challenging 2D example to fold from that chapter (red=mountain, green=valley):
     
(This one works best with a papercutter!)
Here is a link to this and other templates, suitable for classroom use.

Q3. (From my comment:) One can state a higher-dimensional analog, but no one has proven any result in three or higher dimensions.

Q1 & Q2.
These two questions (algorithmic complexity, combinatorial complexity) are two sides
of the same issue. Essentially, neither complexity question has been answered precisely.
However, in some sense the answers are known. The best source is the first paper
on the topic, which precedes the book reference above by a decade (and much was learned
in that decade):

Bern, M., Demaine, E., Eppstein, D., & Hayes, B. "A disk-packing algorithm for an origami magic trick." International Conference on Fun with Algorithms. June. 1998. (Citeseer PDF download)

Here is their paragraph on complexity (the algorithm is based on disk-packing):
   
For local feature size, see the Wikipedia article.
I doubt there could be a complexity bound in terms of $n$, the number of line
segments in the drawing to be folded and cut;
rather, it must depend on the geometry, as does the local feature size.
A: In response to @redhound.
Now updated with step-by-step instructions online:

         


         

The turtle nearly fully folded.
The black lines all align.


         


         

The hole remaining after 1-cut.


