313 eng preprint 1 2020-05-20 2020-05-20 -- We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this existing characterization of the literature to prove that FB is coNP-hard by reducing Partition to the infeasibility of a booking. We further prove that computing a potential-difference maximizing load flow scenario is NP-hard even if we can determine the flow direction a priori. From the literature, it is known that FB can be decided in polynomial time on trees and a single cycle. Thus, our hardness result draws the first line that separates the easy from the hard variants of FB and finally answers that FB is hard in general. under review Creative Commons - CC BY - Namensnennung 4.0 International Johannes Thürauf eng uncontrolled Potential-based flows, Gas networks, Computational complexity, European entry-exit market, Bookings Friedrich-Alexander-Universität Erlangen-Nürnberg B07 https://opus4.kobv.de/opus4-trr154/files/313/booking-complexity-general-preprint-6-4-22.pdf