Complexity Classes & Its Types

Complexity classes are sets of affiliated computational problems. They’re defined in terms of the computational difficulty of working the problems contained within them with respect to particular computational coffers like time or memory. Further formally, the description of a complexity class consists of three effects a type of computational problem, a model of computation, and abounded computational resource. In particular, most complexity classes consist of decision problems that can be solved by a Turing machine with bounded time or space resources.

Some complexity classes are a subset of others. For example, the class of problems solvable in deterministic polynomial time, PP, is a subset of the class of problems solvable in nondeterministic polynomial time NPNP.

Time Complexity: The time complexity of an algorithm is generally used when describing the number of steps it needs to take to solve a problem, but it can also be used to describe how long it takes to certify an answer.

Space Complexity: The space complexity of an algorithm describes how much memory the algorithm needs in order to operate.

Source: https://d3i71xaburhd42.cloudfront.net/d19cce0996d8236b2158123b5c9d98ea0b190e94/15-Figure1-1.png

Complexity classes are helpful for grouping problems that are similar in nature. There are various unresolved problems for many complexity classes, such as whether this complexity class is equal to that complexity class. If the answer is equal in some of these issues, there are tremendous theoretical implications, such as the entire polynomial hierarchy of complexity classes collapsing from hundreds of scenarios to a few, and there are countless practical applications as well. For example, if P = NPP = NP turns out to be true, many of our security algorithms that secure our computers, banks, and other assets will be rendered obsolete.

Computational Complexity

Computational complexity theory is a field of computation theory that investigates the resources, or cost, of computing necessary to solve a particular computational issue in computer science. Computing complexity is the study of the relative computational difficulties of computable functions. The complexity theory considers the difficulty of computational issues in terms of a variety of computational resources. Example: Mowing grass is linearly complex because it takes twice as long to mow twice as much ground. Looking anything up in a dictionary, on the other hand, has merely logarithmic complexity because a double-sized dictionary only needs to be opened once more (exactly in the middle ­ then the problem is cut in half).

Decision Problems

Choice problems are closely related to function problems, which are questions with more sophisticated answers than “yes” or “no.” Every decision problem may be turned into an analogous function problem and vice versa. For example, the decision problem “given two numbers x and y, does x evenly divide y?” and vice versa can be easily translated into the function problem “with two numbers x and y, what is x divided by y?”

A decision procedure of a given decision problem is an effective procedure that determines the response of the decision problem for every value of the parameters in the decision problem. A decision problem is called decidable if there is a decision procedure; otherwise, it is called undecidable. Decidable decision problems are also considered as a subset of natural numbers.

Examples of decidable decision problems are:

• The problem is whether a given number is odd (or even).
• The problem is whether a given number is a prime number.
• The problem is whether a given number is in a specified finite or cofinite subset of natural numbers.

Examples of undecidable decision problems are:

• The halting problem (whether a specified Turing machine halts or runs forever).
• The busy beaver problem (determining the length of the longest halting computation among Turing machines of a specified size).
• Rice’s theorem states that for all non-trivial properties of partial functions, it is undecidable whether a machine computes a partial function with that property.

Deterministic Turing Machine

One of these models is a deterministic one-tape Turing machine. This machine consists of finite state control, a read-write head, and a two-way tape with infinite sequence.

Following is the schematic diagram of a deterministic one-tape Turing machine.

Source:https://www.tutorialspoint.com/design_and_analysis_of_algorithms/images/deterministic_turing_machine.jpg

A program for a deterministic Turing machine specifies the following information −

• A finite set of tape symbols (input symbols and a blank symbol)
• A finite set of states
• A transition function

In algorithmic analysis, if a problem is solvable in polynomial time by a deterministic one-tape Turing machine, the problem belongs to the P class.

Nondeterministic Turing Machine

To solve the computational problem, another model is the Non-deterministic Turing Machine (NDTM). The structure of NDTM is similar to DTM, however here we have one additional module known as the guessing module, which is associated with one write-only head.

Following is the schematic diagram.

Source:https://www.tutorialspoint.com/design_and_analysis_of_algorithms/images/nondeterministic_turing_machine.jpg

If the problem is solvable in polynomial time by a non-deterministic Turing machine, the problem belongs to the NP class.

In our blog, we have talked about 4 types of complexity classes, P, NP, NP-Hard, and NP-Complete.

P

P is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time or polynomial time.

• P is often taken to be the class of computational problems that are “efficiently solvable” or “tractable“.
• Problems that are solvable in theory, but cannot be solved in practice, are called intractable.
• There exist problems in P which are intractable in practical terms; for example, some require at least n1000000 operations.
• P is known to contain many natural problems, including the decision versions of linear programming, calculating the greatest common divisor, and finding a maximum matching.

Knapsack Problem: The knapsack problem belongs to the field of combinatorial optimization. Many more advanced mathematical models of real-world situations include it as a subproblem. Identifying the most restrictive restriction, ignoring the others, solving a knapsack problem, then adjusting the solution to satisfy the disregarded constraints is one basic approach to tough issues.

Algorithm- Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)

for i = 1 to n

do x[i] = 0

weight = 0

for i = 1 to n

if weight + w[i] ≤ W then

x[i] = 1

weight = weight + w[i]

else

x[i] = (W — weight) / w[i]

weight = W

break

return x

Analysis- If the provided items are already sorted into decreasing order of pi/wi, then the while loop takes a time in O(n); Therefore, the total time including the sort is in O(n log n) which is polynomial time.

NP

In computational complexity theory, NP (“Non­deterministic Polynomial-time”) is the set of decision problems solvable in polynomial time on a non­deterministic Turing machine.

It is the set of problems that can be “verified” by a deterministic Turing machine in polynomial time. All the problems in this class have the property that their solutions can be checked effectively.

This class contains all the problems of P class and many problems that people would like to be able to solve effectively, including

• the Boolean satisfiability problem (SAT)
• the Hamiltonian path problem (a special case of TSP)
• the Vertex cover problem.

The term “NP” does not mean “not polynomial.” Originally, the term meant “non-deterministic polynomial. It means according to the one input number of outputs will be produced.

P VS NP

• Every decision problem that is solvable by a deterministic polynomial-time algorithm is also solvable by a polynomial-time non-deterministic algorithm.
• All problems in P can be solved with polynomial-time algorithms, whereas all problems in NP — P are intractable.
• It is not known whether P = NP. However, many problems are known in NP with the property that if they belong to P, then it can be proved that P = NP.
• If P ≠ NP, there are problems in NP that are neither in P nor in NP-Complete.
• The problem belongs to class P if it’s easy to find a solution for the problem. The problem belongs to NP, if it’s easy to check a solution that may have been very tedious to find.

NP-Complete

The NP­complete problems are the most difficult problems in NP (“nondeterministic polynomial time”) in the sense that they are the ones that are most likely not to be in P, according to complexity theory. If someone could uncover a way to solve any NP-complete problem fast (in polynomial time), they could apply that algorithm to all NP problems. Currently, all NP­complete problem algorithms need time that is superpolynomial in the input size.

To solve an NP­complete problem for any nontrivial problem size, generally, one of the following approaches is used:

• Approximation
• Probabilistic
• Special cases
• Heuristic

Some well­known problems that are NP­complete are:

• Boolean satisfiability problem (SAT)
• N­puzzle
• Knapsack problem
• Hamiltonian cycle problem
• Traveling salesman problem
• Subgraph isomorphism problem
• Subset sum problem
• Clique problem
• Vertex cover problem
• Independent set problem
• Graph coloring problem
• Minesweeper

Boolean satisfiability problem: B-SAT is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE.

• Satisfiable: If the Boolean variables can be assigned values such that the formula turns out to be TRUE, then we say that the formula is satisfiable.
• Unsatisfiable: If it is not possible to assign such values, then we say that the formula is unsatisfiable.

CNF- CNF is a conjunction (AND) of clauses, where every clause is a disjunction (OR).

For the CNF value to come TRUE, the value of every clause should be TRUE. Let one of the clauses be (A V B) = TRUE.

If A = 0, B must be 1 i.e. (Ā ⇒ B)

If B = 0, A must be 1 i.e. (Ƀ ⇒ A)

(A V B) = TRUE is equivalent to (Ā ⇒ B) Ʌ (Ƀ ⇒ A)

Now, we can express the CNF as an Implication. So, we create an Implication Graph that has 2 edges for every clause of the CNF.

Thus, for a Boolean formula with ‘m’ clauses, we make an Implication Graph with:

• 2 edges for every clause i.e. ‘2m’ edges.
• 1 node for every Boolean variable involved in the Boolean formula.

Now, 2-SAT limits the problem of SAT to only those Boolean formula which are expressed as a CNF with every clause having only 2 terms(also called 2-CNF).

Consider the following cases:

CASE 1: If edge(X → X̄)

This means (X ⇒ X̄)

If X = TRUE, X̄ = TRUE, which is a contradiction.

But if X = FALSE, there are no implication constraints.

Thus, X = FALSE

CASE 2: If edge(X̄ → X)

This means (X̄ ⇒ X)

IF X̄ = TRUE, X = TRUE, which is a contradiction.

But if X̄ = FALSE, there are no implication constraints.

Thus, X̄ = FALSE i.e. X = TRUE.

CASE 3: If edge(X → X̄) & edge(X̄ → X)

One edge requires X to be TRUE and the other one requires X to be FALSE.

Thus, there is no possible assignment in such a case.

If any two variables X and X̄ are on a cycle i.e. path(Ā → B) & path(Ƀ → A) both exists, then the CNF is unsatisfiable. Otherwise, there is a possible assignment and the CNF is satisfiable.

Note here that, we use path due to the following property of implication:

If we have (A → B) & (B →C), then A → C

Thus, if we have a path in the Implication Graph, that is pretty much same as having a direct edge.

SAT is the first problem that was proven to be NP-complete. This means that all problems in the complexity class NP, which includes a wide range of natural decision and optimization problems, are at most as difficult to solve as SAT. There is no known algorithm that efficiently solves each SAT problem, and it is generally believed that no such algorithm exists; yet this belief has not been proven mathematically, and resolving the question of whether SAT has a polynomial-time algorithm is equivalent to the P versus NP problem, which is a famous open problem in the theory of computing.

NP-Hard

NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally “at least as hard as the hardest problems in NP”. A simple example of an NP-hard problem is the subset sum problem.

A more exact definition is that a problem H is NP-hard if every NP problem L can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, the solution for H can be used to solve L in polynomial time. As a result, discovering a polynomial-time algorithm to tackle an NP-hard problem leads to polynomial-time algorithms for all NP problems. It is doubtful that such an algorithm exists because P NP is suspected.

Here you to satisfy the following points to come into the division of NP-hard

1. If we can solve this problem in polynomial time, then we can solve all NP problems in polynomial time.
2. If you convert the issue into one form to another form within the polynomial time.

Traveling Salesman Problem

The traveling salesman problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one and returning to the same city. The challenge of the problem is that the traveling salesman wants to minimize the total length of the trip.

Proof

To show that TSP is NP-Complete, we must first show that it belongs to NP. In TSP, we locate a tour and verify that it encompasses each vertex only once. The entire cost of the tour’s edges is then computed. Finally, we look to see if the cost is as low as possible. This can be done in a polynomial amount of time. As a result, TSP is a member of NP.

Secondly, we have to prove that TSP is NP-hard. To prove this, one way is to show that the Hamiltonian cycle ≤p TSP (as we know that the Hamiltonian cycle problem is NP-complete).

Assume G = (V, E) to be an instance of the Hamiltonian cycle.

Hence, an instance of TSP is constructed. We create the complete graph G’ = (V, E’), where

E′ = { ( i, j) : i, j ∈ V and i ≠ j

Thus, the cost function is defined as follows −

t (i,j)= {0 if ( i, j) ∈ E

{1 otherwise

Now, suppose that a Hamiltonian cycle h exists in G. It is clear that the cost of each edge in this 0 in G’ as each edge belongs to E. Therefore, h has a cost of 0 in G’. Thus, if graph G has a Hamiltonian cycle, then graph G’ has a tour of 0 costs.

Conversely, we assume that G’ has a tour h’ of cost at most 0. The cost of edges in E’ are 0 and 1 by definition. Hence, each edge must have a cost of 0 as the cost of h’ is 0. We, therefore, conclude that h’ contains only edges in E.

We have thus proven that G has a Hamiltonian cycle, if and only if G’ has a tour of cost at most 0.

Conclusion

The heart of complexity theory, a major issue in theoretical computer science, is complexity classes.

The problem sets P, NP, NP-Complete, and NP-Hard were the subject of this blog. When P=NP, we’ve established a jumping-off point for further research and what-if scenarios.

In Polynomial, P is a collection of issues that a deterministic Turing machine can answer.

Time. A Non-deterministic Turing Machine (NPTM) can answer a set of problems in polynomial time. P is a subset of NP (every issue that can be solved in polynomial time by a deterministic machine can also be solved in polynomial time by a nondeterministic machine), but P≠NP.

Some problems can be translated into one another in such a way that a quick solution to one will result in a quick solution to the other.

There are some problems into which every problem in NP can be translated, and a quick solution to one of these problems will give us a quick answer to every problem in NP.

This category of issues is referred to as NP-complete. Ex:- Clique

If a method for solving a problem may be converted into one for solving any problem (nondeterministic polynomial time), the problem is NP-hard. As a result, NP-hard means “at least as difficult as any NP-problem,” however it could be more difficult.

Briefly after reading, we can conclude a generalized classification as follows:

P problems are quick to solve

NP problems are quick to verify but slow to solve

NP-Complete problems are also quick to verify, slow to solve, and can be reduced to any other NP-Complete problem

NP-Hard problems are slow to verify, slow to solve, and can be reduced to any other NP problem

Finally, if P=NP has proof in the future, humanity will need to develop a new approach to computer security. When this happens, we’ll need a new level of complexity to identify new difficulty levels than we have now.

NOTE: This is a college assignment Blog, where we researched different complexity classes and put them together in this blog.

—ENTC — TYB — B1 — Group 6 —

Roll No. — Name

04 — Ayush Dhandoriya

06 — Dhavanit Gupta

15 — Sanket Gapat

24 — Aditya Gotmare