Efficient Segment Folding is Hard