Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

Abstract

We introduce the Nondeterministic Strong Exponential Time Hypothesis (NSETH) as a natural extension of the Strong Exponential Time Hypothesis (SETH). We show that both refuting and proving NSETH would have interesting consequences.