Casi pratici a 3 sa-sat

Question

Il $ 3-Sat $ È noto che il problema è un problema di completamento NP. Il che significa che (per quanto ho capito), a meno che $ P neq np $, per ogni algoritmo $ A $ che decide $ 3-Sat $, $ A $ Funziona in tempo super polinomiale (so che questo non è ben definito). Un presupposto più forte è il "forte Ipotesi temporale esponenziale "che afferma che ogni algoritmo deve essere eseguito nel peggiore tempo esponenziale.
Ciò significa, ad esempio, che ogni algoritmo $ A $ (Qui mi riferisco a un'implementazione "reale" o pratica, come Glucosi, DPLL, Z3, ecc.), Ha un'istanza di dimensioni, diciamo 200, che $ A $ non sarà in grado di risolvere in un momento ragionevole? Vedo molti solutori SAT risolvere le formule con milioni di variabili in tempo molto breve; e sono a conoscenza dei sottoinsiemi di $ 3-Sat $ che sono facili, come le clausole di corno o un'istanza casuale con una densità nota, ma sembra che questi risolutori funzionino incredibilmente velocemente senza alcuna ipotesi sull'input.
Ho cercato Benchmark sat, o istanze che dovrebbero essere difficili, ma quando li esegui su un moderno risolutore SAT, non sembra essere un problema.
È noto che le ipotesi di complessità (o affermazioni) riguardano il comportamento asintotico, la mia domanda è: sappiamo per quale $ n_0 $ Questi presupposti "iniziano" nel caso di $ 3-Sat $? Possiamo generare o almeno essere sicuri dell'esistenza di una formula relativamente piccola ($< 200$), tale che ogni algoritmo richiede $ SIM2^{200} $ operazioni?