# Tag Info

Accepted

### Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

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, ...
• 10.8k
Accepted

### Enumerating decidable languages

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 (...
• 8,711
Accepted

### Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

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 ...
• 10.8k
Accepted

### Question about algorithm for enumerating minimal AB-separators

tldr: your counterexample is correct. Longer Answer: The way $A$-$B$-separators are defined above the problem to determine whether at least one $A$-$B$-separator exists is NP-complete. In particular ...
• 3,266

### Enumerating decidable languages

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$ ...
• 4,485

### About the decidability of sets enumerated in non decreasing order

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(...
• 29.2k
Accepted

### Definition and Computational Model of EnumP

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 ...
• 2,174