字解扰复杂度类

Question

我在复杂类和相关概念领域的经验并不丰富。但是，输出给定的加扰词是否是真正的英语单词的任务是P问题还是NP问题呢？(如果这有意义的话)我看到的所有程序都会输入并生成单词的所有排列，然后将所有的排列与字典中的每个单词进行比较。如果有另一种算法采取了一种不同的、更有效的方法呢？这会改变问题的类复杂性吗？对不起，如果我使用的术语不正确

Answer 1

你不需要生成所有的排列。只需计算每个字母出现在单词中的次数并比较计数，或者对每个单词的字母排序，然后比较它们。这些运算都是多项式的，所以在P。

Answer 2

生成具有k的单词的排列必然具有指数复杂性，因为有k！排列，算法需要创建所有的排列。但是，使用称为哈希表的数据结构可以使查找部分更高效，这允许在几乎恒定的时间内执行查找。

Answer 3

英语单词的数量是有界的，因此很明显，任何英语单词的可能长度都是有界的，所以从技术上讲，您的问题在固定时间内是可以解决的(尽管常数很大)。如果你把你的问题改写成这样，你会得到一本字母表上任意长的字典，然后你想要确定答案的查询词，那么事情就变得更有趣了。然后，@fbg给出的答案可能是最好的方法；散列每个字母出现次数的元组(例如，按某种排序顺序取字母)，对于字典中的每个单词，然后如果给您一个加扰词并执行相同的哈希操作，您可以非常快地判断您的查询加扰词是否可以被“解密”以给出解决方案，否则字典中就没有解决方案。