Domanda

Un buon esercizio è mostrare $ nc^1 sottoseteq l $. (Secondo il Pagina zoo di complessità Ciò è stato mostrato per la prima volta da Borodin, 1977.) Sebbene i dettagli debbano essere controllati, la prova è semplice: prendere il circuito $ nc^1 $ e fare una prima ricerca sul gate di uscita del circuito. La valutazione ricorsivamente delle porte nel circuito funziona perché la profondità della ricorsione non va mai oltre la profondità del circuito, che è $ log n $.

La mia domanda: lo stesso argomento non mostra che $ ac^1 sottoseteq l $? In questo caso, con ventilatore illimitato, dobbiamo modificare leggermente l'argomento, per assicurarci che stiamo solo memorizzando, ad ogni gate, un puntatore al gate di input corrente su cui stiamo ricordando e il risultato (e o o di tutte le porte di input fino a questo punto. Ma dovrebbe essere ancora $ log n $.

Deve esserci qualcosa di sbagliato in questo argomento, dal momento che non vedo $ ac^1 sottoseteq l $ referenziati da nessuna parte e il Diagramma di inclusione della complessità zoologia Non elenca $ ac^1 $ come sottoinsieme di $ l $ :( Allora, qual è l'errore nel mio pensiero?

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top