Questo è possibile risolvere 3Sat nello spazio O (n^24) e O (1)?

Question

Assumilo n Le variabili numeriche della formula 3CNF data (n≥3) e tutte le clausole nella formula 3CNF data sono diverse.

Ciò significa che per ogni clausola, ogni letterale può essere positivo o negativo ed essere uno dei n variabili, quindi il numero di opzioni per ogni letterale è 2n, ma ogni clausola ha esattamente 3 letterali, quindi il numero massimo di clausole diverse è 2n • 2n • 2n = (2n)³ = 8n³ = O (n³).

ho letto qui Quella formula 3CNF deve avere almeno 8 clausole diverse nella forma:

(x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)

Essere insoddisfatti.

Se questa piccola formula 3CNF è inclusa o sottoinsieme di una formula 3CNF più grande, la formula 3CNF più grande è insoddisfacente di sicuro, a causa di quel sottoinsieme.

Quindi l'algoritmo deve cercare questo sottoinsieme e se l'algoritmo lo ha trovato, l'algoritmo restituisce "la formula data insoddisfacente" come output.

E questo suppone di essere corretto di sicuro.

Ma cosa succede se lo fa l'algoritmonon Trova tale sottoinsieme?

Ciò significa necessariamente che la formula 3CNF data è non unSoddisfabile, cioè soddisfacente?

Poiché il sottoinsieme ha esattamente 8 clausole, l'algoritmo deve iterare attraverso tutti i diversi sottoinsiemi di 8 clausole nella formula 3CNF data.

Se la formula 3CNF data ha m clausole, quindi ci dovrebbero essere θ (m⁸) diversi sottoinsiemi di 8 clausole, ma se tutte le clausole sono diverse, allora m = O (n³), quindi O ((n³)⁸) = O (n^3•8) = O (n²⁴)

Quindi il tempo di esecuzione dell'algoritmo per iterare attraverso tutti questi sottoinsiemi e trovare il sottoinsieme insoddisfacente, se esiste, prende θ (n²⁴) volta.

Per fare ciò, l'algoritmo ha bisogno di 8 interni per loop, dove ciascuno per loop è all'interno dell'altro, con 8 variabili iterative.

Poiché che l'algoritmo non alloca alcuna memoria durante il tempo di esecuzione, la complessità spaziale di questo algoritmo si suppone che sia θ (1).

Fammi sapere se avevo torto e su cosa, cioè se sbaglio allora perché?

Perché mi sbagliavo?

Spiega per favore.

Voglio imparare dagli errori.

penso che

è troppo bello per essere vero

e

Se è troppo bello per essere vero, qualcosa non va.