Let P be the set of problems that can be solved in polynomial time. And an NP(nondeterministic polynomial time) problem be one that can be solved in polynomial time on a non-deterministic machine(Dasgupta et al., 2006).

If a problem is expensive in terms of the running time complexity, it is considered hard. We can then state that an NP-Hard problem is one that a solution is hard to find in finite deterministic steps on a normal Turing machine, however, it can be solved and verified by a Non-Deterministic algorithm/machine in polynomial time.

A deterministic Turing machine takes deterministic/finite steps or actions to get a solution for a given problem X. On the other hand for a Non-deterministic Turing Machine, we deal with problems of indeterministic, infinite actions, meaning a solution may never be reached.

An NP-Complete problem can simply be stated as a decision problem that must be both NP and an NP-hard problem. Given a problem X, for X to be NP-Complete there should be an NP problem Y, such that Y is reducible to X in polynomial time(GeeksforGeeks, 2023). We can then draw a conclusion here that NP-complete problems are at least only solvable or verifiable using a non-deterministic Turing machine.

And if there is no known efficient deterministic algorithm for a problem, however given that there are known non-deterministic algorithms to solve such a problem, we say the problem is NP-Complete.

This set illustration gives a credence to the above definitions:

For a problem to be NP-Complete:

1. It has to be a decision problem
2. It must be both in NP and NP-hard => X is in NP and X is NP-Hard.
3. All NP-complete problems belong to the NP-hard class of problems

Examples of NP-Complete problems:

• The travelling salesperson problem is one commonly identified problem that requires exponential running time to be solved. As an NP-complete problem, the time it takes for the problem to be solved is exponential of the problem size of 'n'. For this reason, the running time increases for exponential-time algorithms making it very inefficient which makes it a Hard-problem to obtain the solution as the problem size 'n' increases.
• Circuit satisfiability is another known NP-complete problem.

Reference:

Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V.(2006). "Algorithms," McGraw-Hill, Boston.

GeeksforGeeks. (2023, January 5). Difference between NP hard and NP Complete Problem. GeeksforGeeks. Retrieved March 15, 2023, from https://www.geeksforgeeks.org/difference-between-np-hard-and-np-complete-problem/