We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [enumeration]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
70 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
678 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 ...
12
votes
0answers
287 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 $...
2
votes
1answer
142 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 (...