什么是NP完全在计算机科学？ [英] What is an NP-complete in computer science?

问题描述

什么是NP完全问题呢？为什么在计算机科学中这样一个重要的话题？

What is an NP-complete problem? Why is it such an important topic in computer science?

推荐答案

NP 代表的的不确定性的多项式的时间。

NP stands for Non-deterministic Polynomial time.

这意味着，这个问题可以在多项式时间使用非确定性图灵机（像一个普通的图灵机，但也包括非确定性的选择功能）来解决。基本上，一个解决方案必须可测试聚的时间。如果是这样的话，和已知的NP问题可以通过给定的问题，修改的输入来解决（一个NP问题可以减少给定的问题），那么问题是NP完全。

This means that the problem can be solved in Polynomial time using a Non-deterministic Turing machine (like a regular Turing machine but also including a non-deterministic "choice" function). Basically, a solution has to be testable in poly time. If that's the case, and a known NP problem can be solved using the given problem with modified input (an NP problem can be reduced to the given problem) then the problem is NP complete.

主要的是要采取远离一个NP完全问题是，它无法解决在多项式时间中任何已知的方法。 NP-硬/ NP完全是示出某些类的问题不可解在现实的时间的一种方式。

The main thing to take away from an NP-complete problem is that it cannot be solved in polynomial time in any known way. NP-Hard/NP-Complete is a way of showing that certain classes of problems are not solvable in realistic time.

编辑：正如其他人所指出的，往往是NP完全问题的近似解。在这种情况下，近似的解决方案通常给出了使用的特殊符号，它告诉我们如何接近的近似是结合一个近似

As others have noted, there are often approximation solutions for NP-Complete problems. In this case, the approximation solution usually gives a approximation bound using special notation which tells us how close the approximation is.

这篇关于什么是NP完全在计算机科学？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！