This extended abstract reports on the computational complexity of reasoning with English sentences featuring temporal prepositions. A fragment of English featuring these constructions, called TPE, is defined by means of a context-free grammar. The phrase-structures which this grammar assigns to the sentences it recognizes can be viewed as formulas of an interval temporal logic, called TPL, whose satisfaction-conditions faithfully represent the meanings of the corresponding English sentences. It is shown that the satisfiability problem for TPL is NEXPTIME-complete.