请解释什么是P问题，NP问题。

题目

请解释什么是P问题，NP问题。

相似考题

1.下面关于NP问题说法正确的是()A.NP问题都是不可能解决的问题B.P类问题包含在NP类问题中C.NP完全问题是P类问题的子集D.NP类问题包含在P类问题中

2.什么是环境问题？请举例说明。

3.若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是（）A、P类问题B、NP难问题C、NP完全问题D、P类语言

4.NP类问题包含在P类问题中。()此题为判断题(对，错)。

参考答案和解析
正确答案: 如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。
NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
更多“请解释什么是P问题，NP问题。”相关问题

  • 第1题：

    什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。


    正确答案:用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。
    用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。
    集合覆盖问题的近似算法采用贪心思想：对于问题，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。

  • 第2题：

    请列举几个常见的NP完全问题。


    正确答案: 1）合取范式的可满足性问题；
    2）三元合取范式的可满足性问题；
    3）团问题；
    4）顶点覆盖问题；
    5）子集和问题；
    6）哈密顿回路问题；
    7）旅行售货员问题。

  • 第3题：

    使用期货来对冲风险，请解释为什么按市场价格定价为什么会产生现金流问题？


    正确答案:期货属于杠杆交易

  • 第4题：

    P问题是可计算问题，NP问题也是可计算问题


    正确答案:正确

  • 第5题：

    邮递员问题，或者叫做最短路径问题是（）。

    • A、P问题
    • B、NP问题
    • C、P和NP问题
    • D、以上都不是

    正确答案:B

  • 第6题：

    何谓P、NP、NPC问题？


    正确答案: 1.P（Polynomial问题）：也即是多项式复杂程度的问题。
    2.NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
    3.NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。

  • 第7题：

    在一个电子企业环境中全球化会带来什么问题?请解释。


    正确答案: 当今世界已经成为一个地球村，商业快速的国际化进程成为电子商务经理的主要关注对象。无论你在哪里，无论你的文化是什么，电子商务可以随时发生。电子商务经理必须意识到这一点并且做好充分的知识准备，进而在这个充满竞争的全球大市场上保持组织的竞争力。

  • 第8题：

    问答题
    什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。

    正确答案： 用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。
    用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。
    集合覆盖问题的近似算法采用贪心思想：对于问题，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。
    解析： 暂无解析

  • 第9题：

    问答题
    请解释什么是P问题，NP问题。

    正确答案： 如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。
    NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
    解析： 暂无解析

  • 第10题：

    问答题
    NP完全问题指的是什么？请举例。

    正确答案： NP完全问题指的是：用目前知道的最好的方法求解，问题求解需要花费的时间（或称为问题求解的复杂性）随问题规模增大以指数关系增长。推销员旅行问题就是一个NP完全问题，我们至今还不知道对NP完全问题是否有花费时间较少的求解方法。例如，可使求解时间随问题规模按多项式关系增长。组合调度问题的求解方法已经应用于交通运输调度、列车编组、空中交通管制和军事指挥自动化等系统。
    解析： 暂无解析

  • 第11题：

    判断题
    P问题是可计算问题，NP问题也是可计算问题
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第12题：

    单选题
    排序问题是属于（）。
    A

    P问题

    B

    NP问题

    C

    P和NP问题

    D

    以上都不是


    正确答案： B
    解析： 暂无解析

  • 第13题：

    下面关于NP问题说法正确的是（）

    • A、NP问题都是不可能解决的问题
    • B、P类问题包含在NP类问题中
    • C、NP完全问题是P类问题的子集
    • D、NP类问题包含在P类问题中

    正确答案:B

  • 第14题：

    写出3个NP完全问题。


    正确答案:团问题、子集和问题、旅行售货员问题。

  • 第15题：

    排序问题是属于（）。

    • A、P问题
    • B、NP问题
    • C、P和NP问题
    • D、以上都不是

    正确答案:A

  • 第16题：

    NP完全问题


    正确答案: 是指用目前知道的最好的方法求解，问题求解需要花费的时间（或称为问题求解的复杂性）随问题规模增大以指数关系增长。

  • 第17题：

    计算学科的根本问题是（）。

    • A、什么能被有效地自动进行
    • B、NP问题
    • C、工程设计
    • D、理论研究实验方法

    正确答案:A

  • 第18题：

    NP完全问题指的是什么？请举例。


    正确答案: NP完全问题指的是：用目前知道的最好的方法求解，问题求解需要花费的时间（或称为问题求解的复杂性）随问题规模增大以指数关系增长。推销员旅行问题就是一个NP完全问题，我们至今还不知道对NP完全问题是否有花费时间较少的求解方法。例如，可使求解时间随问题规模按多项式关系增长。组合调度问题的求解方法已经应用于交通运输调度、列车编组、空中交通管制和军事指挥自动化等系统。

  • 第19题：

    单选题
    邮递员问题，或者叫做最短路径问题是（）。
    A

    P问题

    B

    NP问题

    C

    P和NP问题

    D

    以上都不是


    正确答案： A
    解析： 暂无解析

  • 第20题：

    单选题
    下面关于NP问题说法正确的是（）
    A

    NP问题都是不可能解决的问题

    B

    P类问题包含在NP类问题中

    C

    NP完全问题是P类问题的子集

    D

    NP类问题包含在P类问题中


    正确答案： D
    解析： 暂无解析

  • 第21题：

    名词解释题
    NP完全问题

    正确答案： 是指用目前知道的最好的方法求解，问题求解需要花费的时间（或称为问题求解的复杂性）随问题规模增大以指数关系增长。
    解析： 暂无解析

  • 第22题：

    问答题
    请列举几个常见的NP完全问题。

    正确答案： 1）合取范式的可满足性问题；
    2）三元合取范式的可满足性问题；
    3）团问题；
    4）顶点覆盖问题；
    5）子集和问题；
    6）哈密顿回路问题；
    7）旅行售货员问题。
    解析： 暂无解析

  • 第23题：

    问答题
    何谓P、NP、NPC问题？

    正确答案： 1.P（Polynomial问题）：也即是多项式复杂程度的问题。
    2.NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
    3.NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。
    解析： 暂无解析

相关内容