Хипотеза експоненцијалног времена

У теорији рачунске сложености, хипотеза експоненцијалног времена представља недоказану претпоставку која је формулисана од стране Импаглиација и Патурија 1999. године. Хипотеза тврди да 3-САТ, или било који од неколико сличних НП проблема, не може бити решен у субекспоненцијалном времену у најгорем случају. Хипотеза експоненцијалног времена, ако је истинита, подразумевала би да је П ≠ НП. Могла би да се искористи да се покаже да су многи рачунарски проблеми једнаки у комплексности, у смислу да ако један од њих има алгоритам у субекспоненцијалном времену, сви га имају.

Дефиниција

к-САТ је проблем тестирања да ли Булова формула, у коњуктивној нормалној форми са највише к променљивих, може бити истинита по некој додели булових вредности својим променљивама. За сваки цео број к ≥ 2, дефинисати реални број с_к тако да буде инфимум реалних бројева δ за које постоји алгоритам решавања к-САТ у времену О(2^δн), где је н број променљивих у датој к-САТ инстанци. Тада је с₂ = 0, јер 2-САТ може бити решен у полиномијалном времену. Хипотеза експоненцијалног времена је претпоставка да за свако к > 2, с_к > 0. Јасно, с₃ ≤ с₄ ≤ ..., тако да је еквивалентно претпоставити да је с₃ > 0. Позитивност преосталих бројева с_к следи аутоматски од ове претпоставке.

Неки извори дефинишу хипотезу експоненцијалног времена као мало слабију изјаву да 3-САТ не може бити решен у 2^о(н) времену. Ако би постојао алгоритам који решава 3-САТ проблем у 2^о(н) времену, онда би очито с₃ било једнако нули. Међутим, то је у складу са досадашњим знањем да би могла постојати секвенца 3-САТ алгоритама, свака са временом О(2^δ_ин) за секвенцу бројева δ_и која тежи нули, али где описи ових алгоритама расту тако брзо да најприкладнији алгоритам не би могао аутоматски да се одабере и покрене.

С обзиром да бројеви с₃, с₄, ... формирају монотону секвенцу која је ограничена бројем 1 изнад, морају конвергирати до границе с_∞. Хипотеза јаког експоненцијалног времена (СЕТХ) је претпоставка да ограничавајућа вредност с_∞ секвенце бројева с_к је једнака нули. Друга варијанта је неуниформна хипотеза експоненцијалног времена, која претпоставља да не постоји фамилија алгоритама која може решити 3-САТ у времену 2^о(н).

Импликације задовољења

Није могуће да с_к буде једнак с_∞ бесконачно за било које коначно к. Како су Импаглиацио, Патури и Зејн показали 2001. године, постоји константа α таква да је с_к ≤ с_∞(1 − α/к). Самим тим, ако је хипотеза експоненцијалног времена тачна, мора постојати бесконачно много вредности к за које се с_к разликује од с_к + 1.

Важни појам у овој области је лема проређивања Импаглиација, Патурија и Зејна (2001), која показује да за био које ε > 0, било која к-ЦНФ формула може бити замењена О(2^εн) једноставнијом к-ЦНФ формулом у којој би се свака променљива појављивала само коначан број пута, и самим тим је број чланова коначан. Лема проређивања је доказана понављајућим проналажењима великих скупова тачака које имају непразни заједнички пресек у датој формули, и заменом формуле двема једноставнијим формулама, од којих једна има ове тачке замењене заједничким пресеком, а друга има пресек уклоњен из сваке тачке. Применом леме проређивања и затим коришћењем нових променљивих како бисмо поделили тачке, једна онда може да добије скуп О(2^εн) 3-ЦНФ формула, свака са линеарним бројем променљивих, таква да је оригинална к-ЦНФ формула задовољавајућа ако и само ако је бар једна од ове три 3-ЦНФ формуле задовољавајућа. Дакле, ако би 3-САТ могао бити решен у субекспоненцијалном времену, могла би се искористити ова редукција како би се решио к-САТ, такође у субекспоненцијалном времену. Еквивалентно, ако је с_к > 0 за било које к > 3, онда је и с₃ > 0, и хипотеза експоненцијалног времена би била истинита.

Гранична вредност с_∞ секвенце бројева с_к је највише једнака сЦНФ, где је сЦНФ инфимум бројева δ таквих да задовољивост везивних формула нормалне форме без лимита дужине може бити решено у О(2^δн). Дакле, ако је хипотеза јаког експоненцијалног времена истинита, онда не би било алгоритма за генералну ЦНФ задовољивост која је значајно бржа у односу на тестирање свих могућих задатака. Међутим, ако хипотеза брзог експоненцијалног времена није тачна, и даље би било могуће за с_ЦНФ да буде једнак јединици.

Импликације за друге проблеме претраге

Хипотеза експоненцијалног времена подразумева да многи други проблеми у класи комплексности СНП немају алгоритме чије је време извршења брже од ц^н за неку константу  ц. Ови проблеми укључују бојење графова, проналажење Хамилтонових циклуса, максималних независних скупова, итд. Насупрот томе, ако иједан од ових проблема има субекспоненцијални алгоритам, онда хипотеза експоненцијалног времена није тачна. Ако се клике или независни скупови логаритамских величина могу наћи у полиномијалном времену, хипотеза експоненцијалног времена није тачна. Самим тим, иако проналажење клика или независних скупова малих величина највероватније није НП комплетно, хипотеза експоненцијалног времена имплицира да су ови проблеми неполиномијални. Уопштено говорећи, хипотеза експоненцијалног времена имплицира да није могуће наћи клике или независне сетове величине к у времену н^о(к). Хипотеза експоненцијалног времена такође имплицира да није могуће решити к-СУМ проблем, у времену 'н^о(к), као и да није могуће наћи скупове са к доминирајућих чворова брже него у нк − о(1) времену.

Хипотеза јаког експоненцијалног времена доводи до уских граница на параметризованој сложености неколико проблема графова. Конкретно, ако је хипотеза јаког експоненцијалног времена тачна, онда би граница оптималног времена за проналажење независних скупова на графу ширине w била (2 − о(1))^wн^О(1), оптимално време за доминирајући проблем скупова (3 − о(1))^wн^О(1) а оптимално време за к бојење је (к − о(1))^wн^О(1). Еквивалентно, било какво побољшање у овим временима извршења би оповргнула хипотезу јаког експоненцијалног времена.

Импликације у структуралној комплексности

Ако је хипотеза експоненцијалног времена тачна, онда 3-САТ не би имао алгоритам у полиномијалном времену, што би значило да је П различито од НП. У овом случају, 3-САТ не би чак ни имао алгоритам у квази-полиномијалном времену, па НП не би био ни подскуп од QП. Ипак, ако хипотеза експоненцијалног времена није тачна, не би било импликација за П насупрот НП проблем. Постоје НП комплетни проблеми за које познато најбоље време има форму О(2^нц) за ц < 1, и ако би најбоље могуће време извршавања за 3-САТ било у овом облику, онда би П било различито од НП, јер је 2-САТ Нп комплетно и ова граница није полиномијална, али би хипотеза експоненцијалног времена била нетачна.

У параметризованој теорији комплексности, јер хипотеза експоненцијалног времена имплицира да не постоји алгоритам фиксног параметра за максимум клику, такође имплицира да је W[1] ≠ ФПТ. Ово је битан отворени проблем било да се ова импликација може обрнути: да ли W[1] ≠ ФПТ имплицира хипотезу експоненцијалног времена? Постоји хијерархија параметризованих класа комплексности названа M хијерарија која се меша у W хијерархију у смислу да, за свако и, M[и] ⊆ W[и] ⊆ M[и + 1]. Хипотеза експоненцијалног времена је еквивалентна тврдњи да M[1] ≠ ФПТ, и питање да ли је M[и] = W[и] за и > 1 је такође отворено. Такође је могуће доказати импликације у другом смеру, од неуспеха варијација хипотезе јаког експоненцијалног времена до раздвајања класа комплексности. Како је Вилијамс показао 2010. године, ако постоји алгоритам А који решава Булов круг задовољивости у времену 2^н/ƒ(н) за неке суперполиномијалне растуће функције  ƒ, онда НЕXПТИМЕ није подскуп П/полy.

Литература

• "Еxацт алгоритхмс фор НП-хард проблемс" Архивирано на сајту Wayback Machine (30. септембар 2020)
• "Импровинг еxхаустиве сеарцх имплиес суперполyномиал лоwер боундс"
• Карпински, Марек; Сцхудy, Wаррен (2010). „Фастер Алгоритхмс фор Феедбацк Арц Сет Тоурнамент, Кеменy Ранк Аггрегатион анд Бетwееннесс Тоурнамент”. Алгоритхмс анд Цомпутатион. Лецтуре Нотес ин Цомпутер Сциенце. 6506. стр. 3—14. ИСБН 978-3-642-17516-9. арXив:1006.4396 . дои:10.1007/978-3-642-17517-6_3. 
• "Wхицх проблемс хаве стронглy еxпонентиал цомплеxитy?"