Skip to main content
10 votes
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, ...
Neal Young's user avatar
  • 10.8k
9 votes
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 (...
Lance Fortnow's user avatar
6 votes
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 ...
Neal Young's user avatar
  • 10.8k
5 votes
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 ...
daniello's user avatar
  • 3,266
5 votes

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$ ...
Bjørn Kjos-Hanssen's user avatar
4 votes

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(...
Andrej Bauer's user avatar
  • 29.2k
4 votes
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 ...
holf's user avatar
  • 2,174
2 votes

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

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 ...
holf's user avatar
  • 2,174
1 vote

Help understand why FOL wff are enumerable, but FOL is undecidable

One line of reasoning here is that of Levin Search. https://people.idsia.ch/~juergen/optimalsearch.html The protocol is to try every program in order, and return the first one which “works.” If you ...
Bion Alex Howard's user avatar

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