Ipotesi del tempo esponenziale

Nella teoria della complessità computazionale, l'ipotesi del tempo esponenziale è un'assunzione di difficoltà computazionale non dimostrata, formalizzata da Impagliazzo & Paturi (1999), che afferma che 3-SAT (o uno qualsiasi dei vari problemi NP-completi) non possono essere risolti in tempo subesponenziale nel caso peggiore. L'ipotesi del tempo esponenziale, se fosse vera, implicherebbe che P ≠ NP. Essa può essere usata per dimostrare che molti problemi computazionali sono equivalenti in complessità, nel senso che se uno di essi ha un algoritmo in tempo subesponenziale, allora lo hanno tutti.

Definizione

k-SAT è il problema di verificare se una formula booleana, in forma normale congiuntiva con al massimo k variabili per clausola, può essere resa vera mediante una qualche assegnazione di valori booleani alle sue variabili. Per ciascun intero k ≥ 2, si definisca un numero reale s_k come l'infimo dei numeri reali δ per i quali esiste un algoritmo che risolve k-SAT nel tempo O(2^δn), dove n è il numero di variabili nell'istanza k-SAT data. Allora s₂ = 0, perché 2-SAT può essere risolto in tempo polinomiale. L'ipotesi del tempo esponenziale è la congettura che, per ogni k > 2, s_k > 0. Chiaramente, s₃ ≤ s₄ ≤ ..., così è equivalente assumere che s₃ > 0; la positività dei numeri rimanenti s_k consegue automaticamente da questa assunzione.

Alcune fonti definiscono l'ipotesi del tempo esponenziale come l'affermazione leggermente più debole che 3-SAT non può essere risolto nel tempo 2^o(n). Se esistesse un algoritmo per risolvere 3-SAT nel tempo 2^o(n), allora chiaramente s₃ sarebbe uguale a zero. Tuttavia, è coerente con le attuali conoscenze che ci potrebbe essere una sequenza di algoritmi 3-SAT, ciascuno con il tempo di esecuzione O(2^δ_in) per una sequenza di numeri δ_i che tende a zero, ma in cui le descrizioni di questi algoritmi stanno crescendo così rapidamente che un singolo algoritmo non potrebbe automaticamente selezionare ed eseguire quello più appropriato.

Poiché i numeri s₃, s₄, ... formano una sequenza monotona che è limitata superiormente da uno, essi devono convergere a un limite s_∞. L'ipotesi del tempo esponenziale forte è l'assunzione che il valore limitante s_∞ della sequenza di numeri s_k sia uguale a uno.

Implicazioni per la soddisfacibilità

Non è possibile per s_k essere uguale a s_∞ per qualsiasi k finito: come mostrarono Impagliazzo, Paturi & Zane (2001), esiste una costante α tale che s_k ≤ s_∞(1 − α/k). Perciò, se l'ipotesi del tempo esponenziale è vera, devono esserci infinitamente molti valori di k per i quali s_k differisce da s_k + 1.

Un importante strumento in questo campo è il lemma di sparsificazione di Impagliazzo, Paturi & Zane (2001), che mostra che, per qualsiasi ε > 0, qualsiasi formula k-FCN può essere sostituita da O(2^εn) più delle formule k-FNC in cui ciascuna variabile appare solo un numero costante di volte, e in cui perciò il numero di clausole è lineare. Il lemma di sparsificazione si dimostra trovando ripetutamente grandi insieme di clausole che hanno un'intersezione comune non vuota in una data formula, e sostituendo la formula con due formule più semplici, una delle quali ha ciascuna di queste clausole sostituite dalla loro intersezione comune e l'altra delle quali ha l'intersezione rimossa da ciascuna clausola. Applicando il lemma di sparsificazione e poi usando nuove variabili per spezzare le clausole, si può allora ottenere un insieme di formule O(2^εn) 3-FNC, ciascuna con un numero lineare di variabili, tale che l'originale formula k-CNF è soddisfacibile se e solo se almeno una di queste formule 3-FNC è soddisfacibile. Perciò, se 3-SAT potesse essere risolto in tempo in subesponenziale, si potrebbe usare questa riduzione per risolvere anche k-SAT in tempo subesponenziale. In modo equivalente, se s_k > 0 per qualsiasi k > 3, allora pure s₃ > 0, e l'ipotesi del tempo esponenziale sarebbe vera.

Il valore limitante s_∞ della sequenza di numeri s_k è al massimo uguale a s_FNC, dove s_FNC è l'infimo dei numeri δ tale che la soddisfacibilità delle formule in forma normale congiuntiva senza limiti alla lunghezza della clausole può essere risolto without nel tempo O(2^δn). Perciò, se l'ipotesi del tempo esponenziale forte è vera, allora non ci sarebbe alcun algoritmo per la soddisfacibilità generale FNC che sia significativamente più veloce del verificare tutte le possibili assegnazioni di verità. Tuttavia, se l'ipotesi del tempo esponenziale forte fallisce, sarebbe ancora possibile che s_CNF sia uguale a uno.

Implicazioni per altri problemi di ricerca

L'ipotesi del tempo esponenziale implica che molti altri problemi nella classe di complessità SNP non hanno algoritmi il cui tempo si esecuzione sia più veloce di cⁿ per una qualche costante c. Questi problemi comprendono la k-colorabilità dei grafi, il trovare i cicli hamiltoniani, le cricche massime, i massimi insiemi indipendenti e la copertura dei vertici sui grafi con n vertici. Per converso, se uno qualsiasi di questi problemi avesse un algoritmo subesponenziale, allora si potrebbe dimostrare che l'ipotesi del tempo esponenziale è falsa.

Se le cricche o gli insiemi indipendenti di dimensione logaritmica potessero essere trovati in tempo polinomiale, l'ipotesi del tempo esponenziale sarebbe falsa. Perciò, anche se è improbabile che trovare cricche o insiemi indipendenti di dimensione così piccola sia NP-completo, l'ipotesi del tempo esponenziale implica che questi problemi siano non polinomiali. Più in generale, l'ipotesi del tempo esponenziale implica che non è possibile trovare cricche o insiemi indipendenti di dimensione k nel tempo n^o(k). L'ipotesi del tempo esponenziale implica anche che non è possibile risolvere il problema k-SUM (dati n numeri reali, trovare k di essi che danno come somma zero) nel tempo n^o(k). L'ipotesi del tempo esponenziale forte implica che non è possibile trovare insiemi dominanti con k vertici più rapidamente che nel tempo n^k − o(1).

L'ipotesi del tempo esponenziale forte conduce a limiti rigidi sulla complessità parametrizzata di parecchi problemi di grafi con ampiezza d'albero limitata. In particolare, se L'ipotesi del tempo esponenziale forte è vera, allora il limite del tempo ottimale per trovare insiemi indipendenti sui grafi con ampiezza d'albero w è (2 − o(1))^wn^O(1), il tempo ottimale per il problema degli insiemi dominanti è (3 − o(1))^wn^O(1), il tempo ottimo per il taglio massimo è (2 − o(1))^wn^O(1), e il tempo ottimo per la k-colorazione è (k − o(1))^wn^O(1). In modo equivalente, qualsiasi miglioramento su questi tempi di esecuzione falsificherebbe l'ipotesi del tempo esponenziale forte. L'ipotesi del tempo esponenziale implica anche che qualsiasi algoritmo trattabile a parametro fisso per la copertura delle cricche degli spigoli debba avere dipendenza doppio esponenziale dal parametro.

Implicazioni nella complessità della comunicazione

Nel problema della disgiuntività degli insiemi con tre parti nella complessità della comunicazione, sono specificati tre sottoinsiemi degli interi in un qualche intervallo [1,m], e tre parti comunicanti conoscono ciascuna due dei tre sottoinsiemi. L'obiettivo è che le parti si trasmettano l'un l'altra alcuni bit su un canale di comunicazione condiviso affinché una delle parti sia in grado di determinare se l'intersezione dei tre insiemi è vuota o non vuota. Sarebbe necessario un protocollo di comunicazione banale da m bit affinché una delle tre parti trasmetta un vettore di bit descrivendo l'intersezione dei due insiemi noti a quella parte, dopo di che l'una o l'altra delle due parti rimanenti possono determinare il vuoto dell'intersezione. Tuttavia, se esiste un protocollo che risolve il problema con la comunicazione o(m) e la compitazione 2^o(m), potrebbe essere trasformato in un algoritmo per risolvere k-SAT nel tempo O(1,74ⁿ) per qualsiasi costante fissa k, violando l'ipotesi del tempo esponenziale forte. Perciò, l'ipotesi del tempo esponenziale forte implica o che il protocollo banale per la disgiuntività degli insiemi com tre parti sia ottimale, o che qualsiasi protocollo migliore richieda una quantità esponenziale di computazione.

Implicazioni nella complessità strutturale

Se l'ipotesi del tempo esponenziale è vera, allora 3-SAT non avrebbe un algoritmo in tempo polinomiale, e perciò ne conseguirebbe che P ≠ NP. In modo più forte, in questo caso, 3-SAT non potrebbe nemmeno avere un algoritmo in tempo quasi-polinomiale, così NP non sarebbe un sottoinsieme di QP. Tuttavia, se l'ipotesi del tempo esponenziale fallisce, ciò non avrebbe alcuna implicazione per il problema P contro NP. Esistono problemi NP-completi per i quali i tempi di esecuzione più noti hanno la forma O(2^nc) per c < 1, e se il miglior tempo di esecuzione possibile per 3-SAT fosse in questa forma, allora P sarebbe diverso da NP (perché 3-SAT è NP-completo e questo limite temporale non è polinomiale), ma l'ipotesi del tempo esponenziale sarebbe falsa.

Nella teoria della complessità parametrizzata, poiché l'ipotesi del tempo esponenziale implica che non esiste un algoritmo trattabile a parametri fissi per la cricca massima, ciò implica anche che W[1] ≠ FPT. È un importante problema aperto in questo campo se questa implicazione possa essere invertita: W[1] ≠ FPT implica l'ipotesi del tempo esponenziale? C'è una gerarchia di classi di complessità parametrizzata chiamata gerarchia M che interfoglia la gerarchia W nel senso che, per tutte le i, M[i] ⊆ W[i] ⊆ M[i + 1]; ad esempio, il problema di trovare una copertura dei vertici di dimensione k log n in un grafo a n vertici con parametro k è completo per M[1]. L'ipotesi del tempo esponenziale è equivalente all'affermazione che M[1] ≠ FPT, e anche la domanda se M[i] = W[i] per i > 1 è aperta.

È anche possibile dimostrare le implicazioni nell'altra direzione, dal fallimento di una variazione dell'ipotesi del tempo esponenziale forte alle separazioni delle classi di complessità. Come mostra Williams (2010), se esiste un algoritmo A che risolve la soddisfacibilità dei circuiti booleani nel tempo 2ⁿ/ƒ(n) per una qualche funzione polinomialmente crescente ƒ, allora NEXPTIME non è un sottoinsieme di P/poly. Williams mostra che, se l'algoritmo A esiste, e se esistesse anche una famiglia di circuiti che simula NEXPTIME in P/poly, allora l'algoritmo A potrebbe essere composto con i circuiti per simulare i problemi di NEXPTIME non deterministicamente in una quantità minore di tempo, violando il teorema della gerarchia temporale. Perciò, l'esistenza dell'algoritmo A dimostra l'inesistenza della famiglia dei circuiti e la separazione di queste due classi di complessità.

Bibliografia

• Jianer Chen, Xiuzhen Huang, Iyad A. Kanj e Ge Xia, Strong computational lower bounds via parameterized complexity, in Journal of Computer and System Sciences, vol. 72, n. 8, 2006, pp. 1346–1367, DOI:10.1016/j.jcss.2006.04.007.
• Marek Cygan, Marcin Pilipczuk e Michał Pilipczuk, Known algorithms for EDGE CLIQUE COVER are probably optimal, in Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), 2013, arXiv:1203.1754 (archiviato dall'url originale il 16 aprile 2013).
• Evgeny Dantsin e Alexander Wolpert, On moderately exponential time for SAT, in Theory and Applications of Satisfiability Testing–SAT 2010, Lecture Notes in Computer Science, vol. 6175, Springer-Verlag, 2010, pp. 313–325, DOI:10.1007/978-3-642-14186-7_27.
• Uriel Feige e Joe Kilian, On limited versus polynomial nondeterminism, in Chicago Journal of Theoretical Computer Science, vol. 1, 1997, pp. 1–20.
• Jörg Flum e Martin Grohe, 16. Subexponential Fixed-Parameter Tractability, in Parameterized Complexity Theory, EATCS Texts in Theoretical Computer Science, Springer-Verlag, 2006, pp. 417–451, ISBN 978-3-540-29952-3.
• Russell Impagliazzo e Ramamohan Paturi, The Complexity of k-SAT, in Proc. 14th IEEE Conf. on Computational Complexity, 1999, pp. 237–240, DOI:10.1109/CCC.1999.766282.
• Russell Impagliazzo, Ramamohan Paturi e Francis Zane, Which problems have strongly exponential complexity?, in Journal of Computer and System Sciences, vol. 63, n. 4, 2001, pp. 512–530, DOI:10.1006/jcss.2001.1774, CiteSeerX: 10.1.1.66.3717.
• Daniel Lokshtanov, Dániel Marx e Saket Saurabh, Known algorithms on graphs of bounded treewidth are probably optimal (PDF), in Proc. 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA 2011), 2011, pp. 777–789, arXiv:1007.5450. URL consultato il 16 marzo 2014 (archiviato dall'url originale il 18 ottobre 2012).
• Mihai Pătraşcu e Ryan Williams, On the possibility of faster SAT algorithms (PDF), in Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010), 2010, pp. 1065–1075.
• Ryan Williams, Improving exhaustive search implies superpolynomial lower bounds, in Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010), New York, NY, USA, ACM, 2010, pp. 231–240, DOI:10.1145/1806689.1806723.
• Gerhard Woeginger, Exact algorithms for NP-hard problems: A survey (PDF), in Combinatorial Optimization — Eureka, You Shrink!, vol. 2570, Springer-Verlag, 2003, pp. 185–207, DOI:10.1007/3-540-36478-1_17. URL consultato il 16 marzo 2014 (archiviato dall'url originale il 30 settembre 2020).