Ipotesi del tempo esponenziale

Da Wikipedia, l'enciclopedia libera.

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 correlati) non possono essere risolti in tempo subesponenziale nel caso peggiore.[1] 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[modifica | modifica wikitesto]

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 relae sk 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'istanzak-SAT data. Allora s2 = 0, perché 2-SAT può essere risolto in tempo polinomiale. L'ipotesi del tempo esponenziale è la congettura che, per ogni k > 2, sk > 0. Chiaramente, s3 ≤ s4 ≤ ..., così è equivalente assumere che s3 > 0; la positività dei numeri rimanenti sk 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 2o(n). Se esistesse un algoritmo per risolvere 3-SAT nel tempo 2o(n), allora chiaramente s3 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ì raapidamente che un singolo algoritmo non potrebbe automaticamente selezionare ed eseguire quello più appropriato.[2]

Poiché i numeri s3, s4, ... 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 sk sia uguale a uno.[3]

Implicazioni per la soddisfacibilità[modifica | modifica wikitesto]

Non è possibile per sk essere uguale a s per qualsiasi k finito: come mostrarono Impagliazzo, Paturi & Zane (2001), esiste una costante α tale che sk ≤ s(1 − α/k). Perciò, se l'ipotesi del tempo esponenziale è vera, devono esserci infinitamente molti valori di k per i quali sk differisce da sk + 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 sk > 0 per qualsiasi k > 3, allora pure s3 > 0, e l'ipotesi del tempo esponenziale sarebbe vera.[1][4]

Il valore limitante s della sequenza di numeri sk è al massimo uguale a sFNC, dove sFNC è 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 sCNF sia uguale a uno.[5]

Implicazioni per altri problemi di ricerca[modifica | modifica wikitesto]

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 cn 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.[1][4]

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.[1][6] Più in generale, l'ipotesi del tempo esponenziale implica che non è possibile trovare cricche o insiemi indipendenti di dimensione k nel tempo no(k).[7] 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 no(k). L'ipotesi del tempo esponenziale forte implica che non è possibile trovare insiemi dominanti con k vertici più rapidamente che nel tempo nk − o(1).[5]

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))wnO(1), il tempo ottimale per il problema degli insiemi dominanti è (3 − o(1))wnO(1), il tempo ottimo per il taglio massimo è (2 − o(1))wnO(1), e il tempo ottimo per la k-colorazione è (k − o(1))wnO(1). In modo equivalente, qualsiasi miglioramento su questi tempi di esecuzione falsificherebbe l'ipotesi del tempo esponenziale forte.[8] 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.[9]

Implicazioni nella complessità della comunicazione[modifica | modifica wikitesto]

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 2o(m), potrebbe essere trasformato in un algoritmo per risolvere k-SAT nel tempo O(1,74n) 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.[5]

Implicazioni nella complessità strutturale[modifica | modifica wikitesto]

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(2nc) 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.[7] È 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.[2]

È 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 2n/ƒ(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à.

Note[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]