Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [enumeration]

The tag has no usage guidance.

1
vote
0answers
59 views

Complexity of enumerating over promise problems and circuits?

Given an enumeration over all Turing Machine which run with increasing length, is there a ``complexity class'' which describes the complexity of determining whether a given TM satisfies the promise ...
4
votes
2answers
545 views

Enumerating decidable languages

[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.] Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a ...
7
votes
0answers
171 views

Reference request: exponential growth rates of subsequence-closed languages are integers

This question is migrated from MathOverflow, where it did not receive any answers a year ago. For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $...
3
votes
1answer
124 views

Definition and Computational Model of EnumP

Valiant [1] defined the $P$-enumerable problem in which he used the Counting Turing Machine Model: A counting Turing machine is a standard nondeterministic TM with an auxiliary output device that (...