简答题

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

正确答案

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

答案解析

相似试题
  • 什么是NP类问题?请举例说明。

    简答题查看答案

  • P问题是可计算问题,NP问题也是可计算问题

    判断题查看答案

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

    简答题查看答案

  • 若L是一个NP完全问题,L经过多项式时间变换后得到问题l,则l是()

    单选题查看答案

  • 下面关于NP问题说法正确的是()

    单选题查看答案

  • 写出3个NP完全问题。

    简答题查看答案

  • 请简要解释什么是分辨率?

    简答题查看答案

  • 一个运算符重载函数被定义为成员函数或友员函数,从定义方式、解释方式和调用方式上有何区别?可能会出现什么问题?

    简答题查看答案

  • 说明beq指令的含义,并解释为什么汇编程序在对下列汇编源程序中的beq指令进行汇编时会遇到问题,应该如何修改该程序段?

    简答题查看答案