The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial

Leonard Pitt, Manfred K. Warmuth

Browse the full STOC paper archive.