10

EDIT: Added Lemma 2 which covers all cases asked about. Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing number of 1's, with the time taken between each word and the next polynomial in $n$ and the size of the DFA. Proof. Here's the ...


9

You can enumerate exactly the decidable languages. I've given this question as a homework problem so I'll just give a hint here: You can modify a TM $M$ to a machine $M'$ such that if $M$ is total (halts on all inputs) then $L(M')=L(M)$ and if $M$ is not total then $L(M')$ is finite. By request I'm burning the homework question and putting in the full proof....


6

Theorem 1. The given problem is NP-hard, by reduction from MAX-CUT. Proof. Call the given problem Positive Discrepancy Cut (PDC). Define weighted PDC to be the generalization where the input is a graph $G=(V,E)$ with polynomially bounded (possibly negative) integer edge weights, and the goal is to determine whether there is a positive-weight cut. To prove ...


5

While @LanceFortnow answered the question asked, since the OP mentioned deciders, I'll mention what kind of oracle is needed for that. Jockusch showed that the computable sets are $A$-uniform iff $A$ is of high Turing degree: $$A'\ge_T\emptyset''.$$ So it doesn't imply solving the halting problem, $$A\ge_T\emptyset'.$$ See Soare's book "Recursively ...


4

Suppose there were a computable $f$ as described in the question. Then we could solve the Halting problem as follows. Given a Turing machine $T$, consider the computable function $g$, defined by $$g(k) = \begin{cases} 1 & \text{if $T$ halts in $\leq k$ steps} \\ 0 & \text{otherwise} \end{cases}$$ This is a computable, nondecreasing and total ...


4

First, you have to know that enumeration complexity is not as cleanly defined as other fields of complexity theory. People are still looking for the right definitions. Notions of reductions or completeness for example do not seem to generalize well. You will then have plenty of different names and notations for the same thing depending on the authors. For ...


2

After discussing it further with a3nm, I propose an algorithm that is different than Neal's algorithm and works in a more general setting. The approach gives polynomial delay algorithm but it uses exponential space. The only two properties that we will be using are : (1) The problem is self-reducible, in the sense that if I am given an automaton $A$ and $u \...


Only top voted, non community-wiki answers of a minimum length are eligible