This paper makes two primary contributions. First, we introduce the concept of counting martingales and use it to define counting measures, counting dimensions, and counting strong dimensions. Second, we apply these new tools to strengthen previous circuit lower bounds.

Resource-bounded measure and dimension have traditionally focused on deterministic time ... more >>>