Хипотеза за експоненциалното време (ETH)

Хипотезата за експоненциалното време (Exponential Time Hypothesis - ETH) е фундаментална концепция в теоретичните компютърни науки и изчислителната сложност. Тя постулира, че класическият NP-пълен проблем за изпълнимост на булеви формули (3-SAT) не може да бъде решен за субекспоненциално време в най-лошия възможен случай, служейки като крайъгълен камък за класификацията на алгоритмичните бариери.