## What is an NP-complete in computer science?

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

1 Answer

Hossein Yazdanfar
Punditsdkoslkdosdkoskdo

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

**NP** stands for ** Non-deterministic Polynomial** time.

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.

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.

Edit: 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.