代码之家  ›  专栏  ›  技术社区  ›  little_monster

每种语言都属于P还是NP?

np turing-machines complexity-theory
  •  1
  • little_monster  · 技术社区  · 10 年前

    为什么我要读迈克尔·西瑟的《计算理论》一书,我有一个小问题:每种语言都属于P还是NP?

    1 回复  |  直到 10 年前
        1
  •  1
  •   templatetypedef    10 年前

    不,不是所有的语言都是P或NP。这里有几种方法可以看到这一点:

    1. 在P和NP中有无数种语言,但只有无数种语言。这特别意味着,如果你随机选择一种语言,概率为1,你选择的语言不是P或NP。

    2. P和NP中的所有语言都是可判定的。任何不可判定的语言,如停顿问题,都不可能是NP语言。

    3. 这个 nondeterministic time hierarchy theorem 可以用来表示NEXP中有一些语言不在NP中。

    希望这有帮助!

    推荐文章
    svaerth  ·  使用巨型哈希表在多项式时间内求解数独
    7 年前
    Tamar Geldiashvili  ·  如何检查一行的数据是否在np内部的列表中。where()?
    7 年前
    user3535074  ·  Pandas系列不区分大小写的匹配和值之间的部分匹配
    8 年前
    little_monster  ·  每种语言都属于P还是NP?
    10 年前
    关于  
    代码之家 - 一站式码农服务社区
    沪ICP备11025650号