# Nondeterministic Strong Exponential Time Hypothesis (NSETH)

Jump to navigation
Jump to search

## Target Problem

[[]]

## Description

Refuting unsatisfiable $k$-CNF formulas on $n$ variables requires nondeterministic $2^{n-o(n)}$ time for unbounded $k$.

## Implies the following Hypothesis

## Implied by the following Hypothesis

## Computation Model

## Proven?

No (Variants have been disproved)

## Year

## References/Citation

http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 10