NP-completeness

Algorithms can be classified on different basis. A few of them have been considered below:

  • Type of operations used by the algorithm

      1. Deterministic Algorithms:

        A deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. A deterministic algorithm computes a mathematical function, a function has a unique value for any given input, and the algorithm is a process that produces this particular value as output. Deterministic algorithms can be defined in terms of a state machine: a state describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its initial state or start state. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, and therefore fail to deliver a result. Disadvantages:
        1. Unfortunately, for some problems deterministic algorithms are also hard to find. For example, there are simple and efficient probabilistic algorithms that determine whether a given number is prime and have a very small chance of being wrong. The known deterministic algorithms remain considerably slower in practice.
        2. Another major problem with deterministic algorithms is that sometimes, we don’t want the results to be predictable. For example, if you are playing an on-line game of blackjack that shuffles its deck using a pseudorandom number generator, a clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing him to cheat; for example, the Software Security Group at Reliable Software Technologies was able to do this for an implementation of Texas Hold ’em Poker that is distributed by ASF Software, Inc, allowing them to consistently predict the outcome of hands ahead of time.
        3. Similar problems arise in cryptography, where private keys are often generated using such a generator. This sort of problem is generally avoided using a cryptographically secure pseudo-random number generator.
     
    1. Non-Deterministic Algorithms:

      A non-deterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A non-deterministic algorithm is different from its more familiar deterministic counterpart in its ability to arrive at outcomes using various routes. If a deterministic algorithm represents a single path from an input to an outcome, a non-deterministic algorithm represents a single path stemming into many paths, some of which may arrive at the same output and some of which may arrive at unique outputs. This property is captured mathematically in “non-deterministic” models of computation. Examples: Merge Sort, Spanning Tree
  • On the basis of time taken by algorithm to solve the problem

      1. Polynomial Time Algorithms:

        An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(n^k) for some constant k. Problems for which a polynomial time algorithm exists belong to the complexity class P, which is central in the field of computational complexity theory. Examples: quick sort, basic arithmetic operations etc.
     
    1. Non-Polynomial Time Algorithms:

      This group of algorithms consist of algorithms whose running time is not bounded by polynomial expressions. Example: Travelling salesperson problem
  • Based on the output of algorithms

    1. Decision Problems:

      A decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem “given two numbers x and y, does x evenly divide y?” is a decision problem. The answer can be either ‘yes’ or ‘no’, and depends upon the values of x and y.
    2. Optimization Problems:

      An optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete variables is known as a combinatonial optimization problem. In a combinatorial optimization problem, we are looking for an object such as an integer, permutation or graph from a finite (or possibly countable infinite) set.

These categories should be clear before studying NP-completeness. It helps to go on with the flow of the concepts.

Complexity Classes of Problems

A complexity class is a set of problems of related resource-based complexity. The simpler complexity classes are defined by the following factors:

  • The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on function problems, counting problems, optimization problems etc.
  • The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on non-deterministic Turing machines, boolean circuits, etc.
  • The resource (or resources) that are being bounded and the bounds: These two properties are usually stated together, such as polynomial time, logarithmic space, constant depth, etc.

P-complexity-class:

P, also known as PTIME, is one of the most fundamental complexity classes. It contains all decision problems that can be solved by a deterministic Turing machine in polynomial time.
A language L is in P if and only if there exists a deterministic Turing machine M, such that:

  • M runs for polynomial time on all inputs
  • For all x in L, M outputs 1
  • For all x not in L, M outputs 0

NP-complexity-class:

NP is one of the most fundamental complexity classes. The abbreviation NP refers to "non-deterministic polynomial time."
NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine.
Example: Travelling Salesperson Problem

Hard to solve NP-problems

Because of the many important problems in this class, there have been extensive efforts to find polynomial-time algorithms for problems in NP. However, there remain a large number of problems in NP that defy such attempts, seeming to require super-polynomial time. Whether these problems really aren’t decidable in polynomial time is one of the greatest open questions in computer science.
An important notion in this context is the set of NP-complete decision problems, which is a subset of NP and might be informally described as the "hardest" problems in NP. If there is a polynomial-time algorithm for even one of them, then there is a polynomial-time algorithm for all the problems in NP. Because of this, and because dedicated research has failed to find a polynomial algorithm for any NP-complete problem, once a problem has been proven to be NP-complete this is widely regarded as a sign that a polynomial algorithm for this problem is unlikely to exist.

NP-Hard Problems

To understand this, you should know about reduction. In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is as difficult as the first. Intuitively, problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. We say A is reducible to B. Different types of reduction are discussed in a subsequent section.
Coming to NP-Hard, a problem C can be defined as NP-Hard iff every problem that is in NP is reducible to C.
NP-hard problems are often tackled with rules-based languages in areas such as:

  • Configuration
  • Data mining
  • Selection
  • Diagnosis
  • Process monitoring and control
  • Scheduling etc.

NP-complete Problems

The complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems.
NP-complete is a subset of NP. A problem p in NP is also NP-complete if every other problem in NP can be transformed into p in polynomial time. If any single problem in NP-complete can be solved quickly, then every problem in NP can also be quickly solved, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every problem in NP-complete (that is, it can be reduced in polynomial time). Because of this, it is often said that the NP-complete problems are harder or more difficult than NP problems in general.
Example: Boolean Satisfiability Problem

Satisfiability Problems

  • Boolean Satisfiability Problem: In computer science, Boolean, or propositional, satisfiability (abbreviated SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it establishes if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE. If no such assignments exist, the function expressed by the formula is identically FALSE for all possible variable assignments. In this latter case, it is called unsatisfiable, otherwise satisfiable. For example, the formula “a AND NOT b” is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, “a AND NOT a” is unsatisfiable.
  • Circuit Satisfiability Problem: In theoretical computer science, the circuit satisfiability problem (also known as CIRCUIT-SAT, CircuitSAT, CSAT, etc.) is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true. CircuitSAT has been proven to be NP-complete. In fact, it is a prototypical NP-complete problem; the Cook–Levin theorem is sometimes proved on CircuitSAT instead of on SAT for Boolean expressions and then reduced to the other satisfiability problems to prove their NP-completeness.
  • 3-Satisfiablity: Like the satisfiability problem for arbitrary formulas, determining the satisfiability of a formula in conjunctive normal form where each clause is limited to at most three literals is NP-complete also; this problem is called 3-SAT, 3CNFSAT, or 3-satisfiability. It is used as a starting point for proving that other problems are also NP-hard. This is done by polynomial-time reduction from 3-SAT to the other problem.

Cook-Levin Theorem

The Cook–Levin theorem, also known as Cook’s theorem, states that the Boolean satisfiability problem is NP-complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.
The theorem is named after Stephen Cook and Leonid Levin.
An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP. Crucially, the same follows for any NP complete problem.

Clique Problem

The clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected.
A clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

A clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph).
A maximal clique is a clique to which no more vertices can be added. A maximum clique is a clique that includes the largest possible number of vertices, and the clique number ω(G) is the number of vertices in a maximum clique of G.

Vertex Cover

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. It is an NP-complete problem.
Formally, a vertex cover of a graph G is a set C of vertices such that each edge of G is incident to at least one vertex in C. The set C is said to cover the edges of G. The following figure shows examples of vertex covers in two graphs (and the set C is marked with red).

200px-Vertex-cover.svg

A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number tau is the size of a minimum vertex cover. The following figure shows examples of minimum vertex covers in the previous graphs.

200px-Minimum-vertex-cover.svg

Set Cover

The set covering problem (SCP) is a classical question in computer science and complexity theory.
It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.
Given a set of elements {1,2,…,m} (called the universe) and a set S of n sets whose union equals the universe, the set cover problem is to identify the smallest subset of S whose union equals the universe. For example, consider the universe U = {1, 2, 3, 4, 5} and the set of sets S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: {{1, 2, 3}, {4, 5}}.
In the set covering decision problem, the input is a pair ({U}, {S}) and an integer k; the question is whether there is a set covering of size k or less. In the set covering optimization problem, the input is a pair ({U}, {S}), and the task is to find a set covering that uses the fewest sets.
The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard .

Leave a Reply

Follow

Get notified with the latest posts

Plugin Supporter WordPress Post Navigation
%d bloggers like this: