Question

Un bon exercice consiste à montrer $ nc ^ 1 subseseq l $. (Selon le Page de zoo de complexité Cela a d'abord été montré par Borodin, 1977.) Bien que les détails doivent être vérifiés, la preuve est simple: prenez le circuit $ nc ^ 1 $ et faites la profondeur d'abord sur la porte de sortie du circuit. L'évaluation récursive des portes du circuit fonctionne parce que la profondeur de la récursivité ne va jamais au-delà de la profondeur du circuit, qui est $ log n $.

Ma question: le même argument ne montre-t-il pas que $ ac ^ 1 subseseq l $? Dans ce cas, avec un fan-in illimité, nous devons modifier légèrement l'argument, pour nous assurer que nous ne stockons que, à chaque porte, un pointeur vers la porte d'entrée actuelle sur laquelle nous récurs et le résultat (et ou) de toutes les portes d'entrée jusqu'à ce point. Mais il devrait toujours être $ log n $.

Il doit y avoir quelque chose qui ne va pas avec cet argument, car je ne vois pas $ ac ^ 1 subseseq l $ référencé n'importe où, et le Diagramme d'inclusion de zoologie de la complexité Ne répertorie pas $ ac ^ 1 $ comme sous-ensemble de $ l $ :( Alors, quelle est l'erreur dans ma réflexion?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top