Questions marquées «separation»

Une séparation explicite entre constructibilité temporelle et constructibilité spatiale?

Montrer une fonction qui est constructible dans l'espace mais pas dans le temps.F( n )f(n)f(n) Ce problème est-il lié à une éventuelle séparation entre les classes de complexité DTIME (f (n)) et SPACE (f

Une version descriptive de la complexité du théorème de Rice pourrait-elle être utilisée pour séparer AC0 et PSPACE?

Dans cette question , il a été mentionné qu'il existe des versions de complexité descriptive du théorème de Rice. J'ai trouvé une preuve du théorème suivant: Étant donné une classe de complexité C , les propriétés non triviales des langages en C ne peuvent pas être calculées en C J'avais déjà posté...