La complessità spazio di riconoscere palindromi Watson-Crick

Question

Ho il seguente problema algoritmico:

Determinare lo spazio Turing complessità di riconoscere le stringhe di DNA che sono palindromi Watson-Crick.

palindromi

??Watson-Crick sono stringhe il cui complemento inverso è la stringa originale. Il complemento è definito lettera-saggio, ispirato da DNA:. A è il complemento di T e C è il complemento di G. Un semplice esempio per un WC-palindromo è ACGT

Sono venuto su con due modi di risolvere questo.

Uno richiede $ \ mathcal {} O (n) $ spazio.

• lettura Una volta che la macchina è fatto l'ingresso. Il nastro ingresso deve essere copiato nastro opera in ordine inverso.
• La macchina quindi leggere i nastri di ingresso e di lavoro da sinistra e confrontare ogni voce per verificare la cella nel nastro lavoro è il complimento della cella in ingresso. Ciò richiede $ \ mathcal {} O (n) $ spazio.

L'altro richiede $ \ mathcal {O} (\ log n) $ spazio.

• Durante la lettura dell'ingresso. Contare il numero di voci sul nastro di ingresso.
• lettura Quando il nastro di ingresso è fatto
  • copiare il complemento della lettera sul nastro di lavoro
  • copiare la lettera L alla fine del nastro lavoro
• (Loop punto) Se il contatore = 0, cancellare i sì worktape e di scrittura, poi battuta d'arresto
• Se il nastro di ingresso legge L
  • Spostare la testa input a sinistra per il numero di volte indicato dal contatore (richiede un secondo contatore)
• Se il nastro di ingresso legge R
  • spostare la testina di ingresso a destra per il numero di volte indicato dal contatore (richiede un secondo contatore)
• Se la cella che contiene il valore sul worktape corrisponda alla cella corrente sul nastro d'ingresso
  • decrementare il contatore da due
  • Spostare uno a sinistra oa destra a seconda se R o L è sul worktape rispettivamente
  • copiare il Complemento di L o R alla worktape al posto della L corrente o R
  • continua il ciclo
• Se i valori dont match, cancellare il worktape e scrivere senza, poi battuta d'arresto

Questo viene fuori a circa $ 2 \ log n + 2 $ spazio per la memorizzazione di entrambi i contatori, il complemento corrente, e il valore di L o R.

Il mio problema

Il primo richiede sia tempo lineare e spazio. Il secondo richiede $ \ frac {n ^ 2} {2} $ tempo e $ \ log n $ spazio. Mi è stato dato il problema dal preventivo e si avvicinò con questi due approcci, ma non so quale andare con. Ho solo bisogno di dare spazio alla complessità del problema.

La ragione per cui sto confuso

tenderei a dire la seconda è l'opzione migliore dal momento che è meglio in termini di tempo, ma che la risposta viene solo da me sempre fortunati e venire con un algoritmo. Sembra come se voglio dare la complessità spazio di qualcosa, non richiederebbe fortuna a venire con l'algoritmo giusto. Mi sto perdendo qualcosa? Dovrei anche essere venuta su con una soluzione al problema per rispondere alla complessità spaziale?

Answer 1

responsabilità : Il seguente algoritmo non utilizza il modello standard per sublineare complessità spaziale (vedi WP: DSPACE ), perché scrive al nastro di ingresso. Inoltre l'insieme di (Watson-Crick) palindromi non è in $ \ {mathsf DSPACE} (\ mathcal {} O (1)) = \ {mathsf REG} $. Tuttavia, è una soluzione sul posto per vari scopi pratici (ad esempio, se ogni lettera è una char in C).

Per dimostrare che un problema ha una complessità spazio specifico, quello generalmente ha la necessità di trovare un algoritmo che ha quella complessità spaziale. Questo può richiedere prove ed errori, ma un approccio migliore è quello di avere una buona comprensione del problema che si sta guardando e una buona quantità di esperienza in algoritmi e complessità.

Per questo particolare esempio, v'è un terzo algoritmo che non ha bisogno di spazio aggiuntivo e richiede $ O (n ^ 2) $ complessità temporale. Questo algoritmo sarebbe spazio costante.

Suggerimento:? Perché utilizzare uno spazio aggiuntivo, quando è possibile utilizzare lo spazio occupato dalla ingresso

Suggerimento: zip avanti e indietro attraverso la stringa di controllo di un carattere alla volta - utilizzare lo stato della Macchina di Turing di ricordare quale personaggio si sta verificando e cancellare i caratteri che hai già controllato

.

Answer 2

Il modo in cui viene posta la domanda si dovrebbe trovare una limite superiore e limite inferiore della complessità dello spazio.

La prima parte di solito è fatto con la presentazione di un algoritmo per il vostro problema, ma una riduzione a qualche altro problema ben studiato sarebbe anche il lavoro (e, indirettamente, dare un algoritmo, anche). Dal momento che non si considera una complessità combinata (tempo e spazio) solo le questioni di spazio, anche se il tempo aumenta. Quindi hai trovato un limite superiore di $ \ mathcal {O} (\ log n) $.

La seconda parte è di solito un più complicato molto, ma si può dimostrare facilmente che lo spazio costante non è sufficiente, perché questo renderebbe il vostro linguaggio regolare. Usando il lemma di pompaggio con, ad esempio $ a ^ lb ^ {} 2l a ^ L $, dove $ l $ è il presupposto numero di pompaggio farà il trucco. Questo lascia ancora un ampio divario tra $ \ omega (1) $ e $ \ mathcal {O} (\ log n) $.

Ho trovato un esercizio (vedi Esercizio 6) che dà alcuni suggerimenti. Se interpreto correttamente il loro suggerimento, prova dimostrando che ci sono molte classi di equivalenza diversi del rapporto Myhill-Nerode per ogni dimensione di ingresso. Questo è simile alla tesi secondo cui non è possibile distinguere più di $ c \ cdot \ Gamma ^ {s (n)} $ stringhe di lunghezza $ n $ (dove $ \ Gamma $ è il vostro alfabeto nastro e $ s (n) $ vostro complessità spaziale). Questo vi darà un limite inferiore di $ \ Omega (\ log n) $.

---

Si noti che non è necessario preoccuparsi del complemento di lettere in quanto questa operazione è banale, quindi tutto che funziona per palindromi ordinari possono essere modificati con un paio di stati per risolvere il problema.

Answer 3

E 'estremamente probabile che il classico spazio-tempo compromesso per palindromi detiene anche nel tuo caso. Tale risultato afferma che una macchina di Turing che riconosce palindromi nello spazio $ s $ deve prendere tempo $ \ Omega (n ^ 2 / S) $, vale a dire $$ \ textrm {tempo} \ times \ textrm {spazio} = \ Omega (n ^ 2). $$ Nel tuo caso, il primo algoritmo ha $ TS = \ Theta (n ^ 2) $, e la seconda ha $ TS = \ Theta (n ^ 2 \ log n) $. Si può anche dimostrare che il limite inferiore per lo spazio è $ \ Omega (\ log n) $. Non sono stato in grado di fondare qual è il miglior limite superiore - che è, se c'è un algoritmo utilizzando lo spazio e il tempo logaritmico $ O (n ^ 2 / \ log n) $, o, in generale, per i quali valori di $ S $ possiamo ottenere il tempo $ \ Omega (n ^ 2 / S) $. Come esercizio, si può provare a trovare altri, algoritmi di interpolazione ibridi tuoi due algoritmi.