What is NP-Hard?

In analysis of algorithms we discussed the time complexity of algorithms and how some problems are harder to solve than others. This is a big topic in computer science and is known as the P vs NP problem. The question is which problems can be solved in reasonable time, i.e. polynomial time, while other problems require so much time and resources that solving them becomes infeasible for larger inputs.

Problem Classes

We can assign problems to different classes based on how their time complexity grows with the size of the input. Two of the most common classes are polynomial time and exponential time.

P - Polynomial Time

The class P contains problems that can be solved in polynomial time. This means that the time complexity of the algorithm is $O(n^k)$ for some constant $k$. Don't forget that $n$ is the size of the input and that a problem that is $O(log(n))$ is also in P. This is because the problem is still solvable in polynomial time, as it is an upper bound on the time complexity. Common examples of problems in P are sorting algorithms like quicksort and mergesort.

Exponential Time

Problems that take longer such as $O(2^n)$ or $O(n!)$ are not in P as they grow exponentially with the size of the input. This means that the time it takes to solve the problem increases rapidly as the input size increases. These problems are often infeasible to solve for large inputs. An example of a problem that is in exponential time is the travelling salesman problem.

What is the stuff with the verification in polynomial time? Is mentioned but unsure how exactly need and example

Algorithm Types

Algorithms can primarly be divided into two types, deterministic and non-deterministic.

Deterministic

A deterministic algorithm is an algorithm that, given a specific input, will always produce the same output. This means that the algorithm is predictable and will always produce the same result for the same input. Binary search is an example of a deterministic algorithm as it will always perform the same steps and return the same result for the same input array and target value.

Non-Deterministic

A non-deterministic algorithm is an algorithm that can produce different outputs for the same input. This means that the algorithm is not predictable and can produce different results for the same input. You can think of these algorithms having some randomness in them and might make guesses to find the solution. An example of a non-deterministic algorithm would be if to find a target value in an input array, the algorithm makes random guesses and checks if the guess is correct.

P vs NP

We have already seen which problems are in P and which are not. The question now is which problems are in NP.

The class NP (Non-deterministic Polynomial time) contains problems that can be verified in polynomial time. This means that given a solution to the problem, the solution can be verified if it is correct in polynomial time. Importantly, a problem not being in P does not mean it is in NP. The class NP contains problems that are not necessarily solvable in polynomial time but can be verified in polynomial time, then there are also problems that are not in NP.

This leads to one of the most famous problems in computer science, the P vs NP problem. The question is whether every problem that can be verified in polynomial time can also be solved in polynomial time. This would mean that P = NP. If P = NP, then every problem that can be verified in polynomial time can also be solved in polynomial time. This would be a huge breakthrough in computer science as it would mean that many problems that are currently infeasible to solve but can be verified in polynomial time could be solved in polynomial time.

NP-Complete and NP-Hard

NP Complete is NP-Hard but als has an algo in NP?

But solving one NP-Complete problem in polynomial time means all NP-Complete problems can be solved in polynomial time??? Same goes for if one NP-Hard problem can be solved in polynomial time then all NP problems can be solved in polynomial time?

algdPvsNP.png

Reduction

The conversion of one problem to another has to be in polynomial time???

Boolean Satisfiability Problem (SAT)

CNF (Conjunctive Normal Form) ??? and then reduce to 0/1 Knapsack Problem

Cook-Levin Theorem

The Cook-Levin Theorem is named after it's researchers Stephen Cook and Leonid Levin. The theorem states that the Boolean Satisfiability Problem (SAT) is NP-Complete. This established the first known NP-Complete problem and laid the foundation for showing that many other problems are also NP-Complete which earnt Cook the Turing Award in 1982. Therefore Cook's work showed that if $P=NP$, then SAT (and all NP-Complete problems) can be solved in polynomial time which would be a huge breakthrough in computer science.

BQP

Quantum stuff