Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Intractable Problems(NP-Completeness)

No description

Jayson Vann Banogon

on 8 August 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Intractable Problems(NP-Completeness)

Intractable Problems(NP-Completeness)
MCS 102
Jayson Vann M. Banogon

Intractable Problems
Difference between Undecidable and Intractable Problems
Undecidable problems are those for which no computer solution can ever exist, while intractable problems are those for which there is strong evidence that, although they can be solved by a computer, they cannot be solved sufficiently fast that the solution is truly useful in practice. Understanding this theory, and in particular being able to prove that a problem you are facing belongs to one of these classes, allows you to justify taking another approach — simplifying the problem or writing code to approximate the solution.
Computational Complexity Theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. Examples of complexity classes are P(Polynomial time) and NP(Nondeterministic polynomial time).
A problem is regarded as inherently difficult if its solution requires significant resources(time and storage), whatever the algorithm used.
Thank you!
NP(Nondeterministic Polynomial Time)
Decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters.
NP is the set of decision problems where the "yes"-instances can be accepted in polynomial time by a non-deterministic Turing machine.
NP-hard is a class of problems that are, informally, "at least as hard as the hardest problems in NP".
NP-complete when it is both in NP and NP-hard.
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.
The most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. This means that the time required to solve even moderately sized versions of many of these problems can easily reach into the billions or trillions of years, using any amount of computing power available today.
NP-complete problems are often addressed by using heuristic methods.
The objective of a heuristic is to produce a solution in a reasonable time frame that is good enough for solving the problem at hand. This solution may not be the best of all the actual solutions to this problem, or it may simply approximate the exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.
Examples of NP-Complete Problems
knapsack problem
is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
Application(s): Resource Allocation
Clique problem
refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, sets of elements where each pair of elements is connected. the maximum clique problem arises in the following real-world setting. Consider a social network, where the graph’s vertices represent people, and the graph’s edges represent mutual acquaintance. To find a largest subset of people who all know each other, one can systematically inspect all subsets, a process that is too time-consuming to be practical for social networks comprising more than a few dozen people.
Application(s): Network Redundancy, Network Availability
Graph coloring
is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a
vertex coloring
Application(s): GSM Region Coloring, Map Coloring
Hamiltonian path problem
and the
Hamiltonian cycle problem
are problems of determining whether a
Hamiltonian path
or a
Hamiltonian cycle
exists in a given graph (whether directed or undirected). Both problems are NP-complete.
Hamiltonian path
is a path in an undirected or directed graph that visits each vertex exactly once. A
Hamiltonian cycle
Hamiltonian circuit
) is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.
Application(s): Public Transport, Tour Planning
partition problem
is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2.
Application(s): Load Balancing, Balancing Weight of Cargos for Ships
Given S = {3,1,1,2,2,1}, a valid solution to the partition problem is the two sets S1 = {1,1,1,2} and S2 = {2,3}. Both sets sum to 5, and they partition S. Note that this solution is not unique. S1 = {3,1,1} and S2 = {2,2,1} is another solution.
Intractable Problems
Problems that can be solved in theory (given large but finite time), but which in practice take too long for their solutions to be useful, are known as intractable problems.
Problems that are decidable but require a large amount of time to solve them.
Full transcript