NP - HARD

Information about NP - HARD

Published on March 6, 2009

Author: ankush85

Source: authorstream.com

Content

NP –HARD AND NP – COMPLETE PROBLEMS : 1 NP –HARD AND NP – COMPLETE PROBLEMS BASIC CONCEPTS The computing times of algorithms fall into two groups. Group1– consists of problems whose solutions are bounded by the polynomial of small degree. Example – Binary search o(log n) , sorting o(n log n), matrix multiplication 0(n 2.81). NP –HARD AND NP – COMPLETE PROBLEMS (Contd..) : 2 NP –HARD AND NP – COMPLETE PROBLEMS (Contd..) Group2 – contains problems whose best known algorithms are non polynomial. Example –Traveling salesperson problem 0(n22n), knapsack problem 0(2n/2) etc. There are two classes of non polynomial time problems 1)      NP- hard 2)      NP-complete A problem which is NP complete will have the property that it can be solved in polynomial time iff all other NP – complete problems can also be solved in polynomial time. NP –HARD AND NP – COMPLETE PROBLEMS (Contd..) : 3 NP –HARD AND NP – COMPLETE PROBLEMS (Contd..) If an NP-hard problem can be solved in polynomial time, then all NP-complete problems can be solved in polynomial time. All NP-complete problems are NP-hard, but all NP-hard problems are not NP-complete. The class of NP-hard problems is very rich in the sense that it contain many problems from a wide variety of disciplines. DETERMINISTIC and NONDETERMINISTIC ALGORITHMS : 4 DETERMINISTIC and NONDETERMINISTIC ALGORITHMS Algorithms with the property that the result of every operation is uniquely defined are termed deterministic. Such algorithms agree with the way programs are executed on a computer. In a theoretical framework we can allow algorithms to contain operations whose outcome is not uniquely defined but is limited to a specified set of possibilities. Deterministic and Nondeterministic algorithms (contd..) : 5 Deterministic and Nondeterministic algorithms (contd..) The machine executing such operations are allowed to choose any one of these outcomes subject to a termination condition. This leads to the concept of non deterministic algorithms. To specify such algorithms in SPARKS, we introduce three statements i)      choice (s) ……… arbitrarily chooses one of the elements of the set S. ii)      failure …. Signals an unsuccessful completion. iii)     Success : Signals a successful completion. Deterministic and Nondeterministic algorithms (contd..) : 6 Deterministic and Nondeterministic algorithms (contd..) Whenever there is a set of choices that leads to a successful completion then one such set of choices is always made and the algorithm terminates. A nondeterministic algorithm terminates unsuccessfully if and only if there exists no set of choices leading to a successful signal. A machine capable of executing a non deterministic algorithm is called a non deterministic machine. While non-deterministic machines do not exist in practice they will provide strong intuitive reason to conclude that certain problems cannot be solved by fast deterministic algorithms. Example of a non deterministic algorithm : 7 Example of a non deterministic algorithm // The problem is to search for an element x // // Output j such that A(j) =x; or j=0 if x is not in A // j ?choice (1 :n ) if A(j) =x then print(j) ; success endif print (‘0’) ; failure complexity 0(1); - Non-deterministic decision algorithms generate a zero or one as their output. - Deterministic search algorithm complexity. ?(n) Deterministic and Nondeterministic algorithms (contd..) : 8 Deterministic and Nondeterministic algorithms (contd..) Many optimization problems can be recast into decision problems with the property that the decision problem can be solved in polynomial time iff the corresponding optimization problem can . EXAMPLE : [0/1 knapsack] : The decision is to determine if there is a 0/1 assignment of values to xi 1? i ? n such that ? pixi ? R, and ? wixi ? M, R, M are given numbers pi, wi ?0, 1? i ? n. It is easy to obtain polynomial time non deterministic algorithms for many problems that can be deterministically solved by a systematic search of a solution space of exponential size. SATISFIABILITY : 9 SATISFIABILITY Let x1,x2,x3….xn denotes Boolean variables. _ Let xi denotes the relation of xi. A literal is either a variable or its negation. A formula in the prepositional calculus is an expression that can be constructed using literals and the operators and ? or v. A clause is a formula with at least one positive literal. The satiability problem is to determine if a formula is true for some assignment of truth values to the variables. SATISFIABILITY (Contd..) : 10 SATISFIABILITY (Contd..) It is easy to obtain a polynomial time non determination algorithm that terminates successfully if and only if a given prepositional formula E(x1,x2……xn) is satiable. Such an algorithm could proceed by simply choosing (non deterministically) one of the 2n possible assignments of truth values to (x1,x2…xn) and verify that E(x1,x2…xn) is true for that assignment. Definition of the classes NP-hard and NP-complete : 11 Definition of the classes NP-hard and NP-complete P is the set of all decision problems solvable by a deterministic algorithm in polynomial time. NP is the set of all decision problems solvable by a nondeterministic algorithm in polynomial time. Since deterministic algorithm are a special case of non deterministic ones, we can conclude that P?NP. The most famous unsolved problem in computer science is whether P = NP or P ? NP. Is it possible that for all the problems in NP their exist polynomial time deterministic algorithms which have remained undiscovered ? Definition of the classes NP-hard and NP-complete (contd..) : 12 Definition of the classes NP-hard and NP-complete (contd..) In considering this problem S.COOK formulated the following question : Is there any single problem in NP such that if we showed it to be in P then that would imply that P = NP. COOK’s Theorem : Satisfiability is in P if and only if P = NP. Definition of the classes NP-hard and NP-complete (contd..) : 13 Definition of the classes NP-hard and NP-complete (contd..) Definition : Reducibility Let L1 and L2 be problems. L1 reduces to L2 (L1 ? L2) if and only if there is a deterministic polynomial time algorithm to solve L1 that solves L2 in polynomial time. If L1 ? L2 and L2 ? L3 then L1 ? L3. Definition : NP-Hard Problem : A problem L is NP-hard if any only if satisfiability reduces to L. Definition of the classes NP-hard and NP-complete (contd..) : 14 Definition of the classes NP-hard and NP-complete (contd..) Definition : NP-complete Problem : A problem L is NP-complete if and only if L is NP-hard and L ? NP. There are NP-hard problems that are not NP-complete. Example : Halting problem is NP-hard decision problem, but it is not NP-complete. Halting Problem : To determine for an arbitrary deterministic algorithm A and an input I whether algorithm A with input I ever terminates (or enters an infinite loop). Halting problem is not NP-complete; but NP-hard : 15 Halting problem is not NP-complete; but NP-hard Halting problem is un-decidable. - Hence there exists no algorithm to solve this problem. - So, it is not in NP. - So, it is not NP-complete. Halting problem is NP-hard To show that Halting problem is NP-hard, we show that satisfiability is ? halting problem. For this let us construct an algorithm A whose input is a prepositional formula X. - Suppose X has n variables. - Algorithm A tries out all 2n possible truth assignments and verifies if X is satisfiable. Halting problem is NP-hard (Contd..) : 16 Halting problem is NP-hard (Contd..) - If it is then A stops. - If X is not satisfiable, then A enters an infinite loop. - Hence A halts on input iff X is satisfiable. - If we had a polynomial time algorithm for the halting problem, then we could solve the satisfiability problem in polynomial time using A and X as input to the algorithm for the halting problem . - Hence the halting problem is an NP-hard problem which is not in NP. - So it is not NP-complete. NP-HARD GRAPH AND SCHEDULING PROBLEMS : 17 NP-HARD GRAPH AND SCHEDULING PROBLEMS Some NP-hard Graph Problems : The strategy to show that a problem L2 is NP-hard is Pick a problem L1 already known to be NP-hard. Show how to obtain an instance I1 of L2 from any instance I of L1 such that from the solution of I1 - We can determine (in polynomial deterministic time) the solution to instance I of L1. NP-HARD GRAPH AND SCHEDULING PROBLEMS (contd..) : 18 NP-HARD GRAPH AND SCHEDULING PROBLEMS (contd..) Conclude from (ii) that L1 ? L2. Conclude from (i),(ii), and the transitivity of ? that Satisfiability ? L1 L1 ? L2 ? Satisfiability L2 ? L2 is NP-hard NP-HARD GRAPH AND SCHEDULING PROBLEMS (CONTD..) : 19 NP-HARD GRAPH AND SCHEDULING PROBLEMS (CONTD..) Chromatic Number Decision Problem (CNP) A colouring of a graph G = (V,E) is a function f : V ? { 1,2, …, k} ? i ? V . If (U,V) ?E then f(u) ? f(v). The CNP is to determine if G has a colouring for a given K. Satisfiability with at most three literals per clause ? chromatic number problem. ? CNP is NP-hard. NP-HARD GRAPH AND SCHEDULING PROBLEMS (contd..) : 20 NP-HARD GRAPH AND SCHEDULING PROBLEMS (contd..) Directed Hamiltonian Cycle (DHC) Let G = (V,E) be a directed graph and length n = 1V1 The DHC is a cycle that goes through every vertex exactly once and then returns to the starting vertex. The DHC problem is to determine if G has a directed Hamiltonian Cycle. Theorem : CNF (Conjunctive Normal Form) satisfiability ? DHC ? DHC is NP-hard. NP-HARD GRAPH AND SCHEDULING PROBLEMS (CONTD..) : 21 NP-HARD GRAPH AND SCHEDULING PROBLEMS (CONTD..) Travelling Salesperson Decision Problem (TSP) : The problem is to determine if a complete directed graph G = (V,E) with edge costs C(u,v) has a tour of cost at most M. Theorem : Directed Hamiltonian Cycle (DHC) ? TSP But from problem (2) satisfiability ? DHC ? Satisfiability ? TSP ? TSP is NP-hard. NP-HARD SCHEDULING PROBLEMS : 22 NP-HARD SCHEDULING PROBLEMS 1. Sum of subsets The problem is to determine if A={a1,a2,…….,an} (a1,a2,………,an are positive integers) has a subset S that sums to a given integer M. 2. Scheduling identical processors Let Pi 1=i=m be identical processors or machines Pi. Let Ji 1=i=n be n jobs. Jobs Ji requires ti processing time. NP-HARD SCHEDULING PROBLEMS (Contd..) : 23 NP-HARD SCHEDULING PROBLEMS (Contd..) A schedule S is an assignment of jobs to processors. For each job Ji ,S specifies the time intervals and the processors on which this job is to be processed. A job can not be processed by more than one processor at any given time. The problem is to find a minimum finish time non-preemptive schedule. The finish time of S is FT(S) = max{Ti} 1=i=m Where Ti is the time at which processor Pi finishes processing all jobs (or job segments) assigned to it. SOME SIMPLIIFIED NP-HARD PROBLEMS : 24 SOME SIMPLIIFIED NP-HARD PROBLEMS An NP-hard problem L cannot be solved in deterministic polynomial time. By placing enough restrictions on any NP hard problem, we can arrive at a polynomially solvable problem. Examples. (i) CNF- Satisfiability with at most three literals per clause is NP-hard. If each clause is restricted to have at most two literals then CNF-satisfiability is polynomially solvable. SOME SIMPLIIFIED NP-HARD PROBLEMS : 25 SOME SIMPLIIFIED NP-HARD PROBLEMS (ii)Generating optimal code for a parallel assignment statement is NP-hard, - however if the expressions are restricted to be simple variables, then optimal code can be generated in polynomial time. (iii)Generating optimal code for level one directed a- cyclic graphs is NP-hard but optimal code for trees can be generated in polynomial time. (iv)Determining if a planner graph is three colourable is NP-Hard - To determine if it is two colorable is a polynomial complexity problem. (We only have to see if it is bipartite)

Related presentations


Other presentations created by ankush85

Nanotechnology
03. 04. 2009
0 views

Nanotechnology

Human Resource Management System
06. 03. 2009
0 views

Human Resource Management System

Nanotechnology
27. 03. 2009
0 views

Nanotechnology

INTRODUCTION TO NANOTECHNOLOGY
20. 11. 2009
0 views

INTRODUCTION TO NANOTECHNOLOGY

Nanotechnology in Sports
22. 11. 2009
0 views

Nanotechnology in Sports

Computer Architecture
14. 07. 2009
0 views

Computer Architecture

HR
18. 03. 2009
0 views

HR

Hospital Management System
08. 04. 2009
0 views

Hospital Management System

Welcome to Visual Basic
06. 03. 2009
0 views

Welcome to Visual Basic

HTML
20. 04. 2009
0 views

HTML

Computer Languages
03. 06. 2013
0 views

Computer Languages

Taking Care of Computer
03. 06. 2013
0 views

Taking Care of Computer

Understanding Camera
16. 10. 2012
0 views

Understanding Camera

Photography Technical Terms
25. 09. 2012
0 views

Photography Technical Terms

Basics of Photography
25. 09. 2012
0 views

Basics of Photography

AIR MUSCLES
03. 01. 2012
0 views

AIR MUSCLES

Molecular Nanotechnology
24. 11. 2009
0 views

Molecular Nanotechnology

Nanotech Innovation
22. 11. 2009
0 views

Nanotech Innovation

FINANCIAL  MARKET
16. 05. 2009
0 views

FINANCIAL MARKET

Operating System
19. 04. 2009
0 views

Operating System

Management Control
10. 07. 2009
0 views

Management Control

Accounting Principles
01. 07. 2009
0 views

Accounting Principles

Balance Sheet
21. 07. 2009
0 views

Balance Sheet

Balance Sheet Auditing
01. 07. 2009
0 views

Balance Sheet Auditing

BRANCH AND BOUND
05. 03. 2009
0 views

BRANCH AND BOUND

THE  THREE  BRANCHES  OF GOVERNMENT
13. 06. 2009
0 views

THE THREE BRANCHES OF GOVERNMENT

Structure of Atom
11. 05. 2009
0 views

Structure of Atom

Compression Techniques
05. 03. 2009
0 views

Compression Techniques

DYNAMIC PROGRAMMING
06. 03. 2009
0 views

DYNAMIC PROGRAMMING

Quantum Mechanics
25. 08. 2009
0 views

Quantum Mechanics

Marketing Plan
19. 06. 2009
0 views

Marketing Plan

Book Keeping
24. 06. 2009
0 views

Book Keeping

DFDS
02. 10. 2008
0 views

DFDS

Semiconductors
25. 04. 2009
0 views

Semiconductors

Organic  Chemistry
28. 04. 2009
0 views

Organic Chemistry

Atoms Molecules and Ions
17. 06. 2009
0 views

Atoms Molecules and Ions

Covalent Bond
25. 04. 2009
0 views

Covalent Bond

Cost Accounting Standards
25. 06. 2009
0 views

Cost Accounting Standards

Crisis Management
19. 06. 2009
0 views

Crisis Management

Marketing
18. 03. 2009
0 views

Marketing

Business Strategy
27. 04. 2009
0 views

Business Strategy

Time Management
23. 03. 2009
0 views

Time Management

Networking Protocols
23. 05. 2009
0 views

Networking Protocols

Network Layer
23. 05. 2009
0 views

Network Layer

Final Accounts
24. 06. 2009
0 views

Final Accounts

ARTIFICIAL  INTELLIGENCE
03. 04. 2009
0 views

ARTIFICIAL INTELLIGENCE

Play with C
08. 04. 2009
0 views

Play with C

Software Development Cycle
23. 03. 2009
0 views

Software Development Cycle

THE GREEDY METHOD
06. 03. 2009
0 views

THE GREEDY METHOD

JOB SEQUENCING
06. 03. 2009
0 views

JOB SEQUENCING

Electricity and Magnetism
29. 04. 2009
0 views

Electricity and Magnetism

Optical Fiber
24. 05. 2009
0 views

Optical Fiber

Quality Assurance
06. 03. 2009
0 views

Quality Assurance

Object-oriented Design
11. 04. 2009
0 views

Object-oriented Design

A.R. Rahman
08. 03. 2009
0 views

A.R. Rahman

Hollywood Female Celebrities
13. 03. 2009
0 views

Hollywood Female Celebrities

Flow nets
04. 09. 2009
0 views

Flow nets

Energy and Nanotechnology
22. 11. 2009
0 views

Energy and Nanotechnology

LOGIC  DESIGN
06. 03. 2009
0 views

LOGIC DESIGN

VB-IDE
06. 03. 2009
0 views

VB-IDE

DLF IPL FINAL
25. 05. 2009
0 views

DLF IPL FINAL

MINIMUM SPANNING TREES
06. 03. 2009
0 views

MINIMUM SPANNING TREES

CPU Scheduling
05. 03. 2009
0 views

CPU Scheduling

Virtual Memory
05. 03. 2009
0 views

Virtual Memory

POK
09. 05. 2009
0 views

POK

2D Transformations
05. 03. 2009
0 views

2D Transformations

Greedy Algorithms
05. 03. 2009
0 views

Greedy Algorithms

BACKTRACKING
05. 03. 2009
0 views

BACKTRACKING

DIVIDE And CONQUER
06. 03. 2009
0 views

DIVIDE And CONQUER

ELEMENTARY DATA STRUCTURES
06. 03. 2009
0 views

ELEMENTARY DATA STRUCTURES

JPEG Compression
06. 03. 2009
0 views

JPEG Compression

Mpeg-compression
06. 03. 2009
0 views

Mpeg-compression

TRAVELLING SALESPERSON PROBLEM
06. 03. 2009
0 views

TRAVELLING SALESPERSON PROBLEM

VBA Introduction
06. 03. 2009
0 views

VBA Introduction

Introduction to Java
09. 03. 2009
0 views

Introduction to Java

Java  Basics
09. 03. 2009
0 views

Java Basics

Heuristic Search
13. 03. 2009
0 views

Heuristic Search

HSM
19. 03. 2009
0 views

HSM

Tata's  Nano  Car
25. 03. 2009
0 views

Tata's Nano Car

Air Cranes
08. 04. 2009
0 views

Air Cranes

Newborn Care
10. 04. 2009
0 views

Newborn Care

Photosynthesis Process
10. 04. 2009
0 views

Photosynthesis Process

ActionScript
13. 04. 2009
0 views

ActionScript

Xml
15. 04. 2009
0 views

Xml

Snakes mis use
17. 04. 2009
0 views

Snakes mis use

Php Web Development
21. 04. 2009
0 views

Php Web Development

Cricket Intro
21. 04. 2009
0 views

Cricket Intro

Cricket Umpiring and Rules
21. 04. 2009
0 views

Cricket Umpiring and Rules

Arm and Forearm
23. 04. 2009
0 views

Arm and Forearm

Elements Ions Isotopes
25. 04. 2009
0 views

Elements Ions Isotopes

Chemical Bond
25. 04. 2009
0 views

Chemical Bond

Discovering Newtons Laws
29. 04. 2009
0 views

Discovering Newtons Laws

FreeFall
29. 04. 2009
0 views

FreeFall

Digital photography
26. 04. 2009
0 views

Digital photography

Health Effects of Alcohol
26. 04. 2009
0 views

Health Effects of Alcohol

Poetry Terminology
27. 04. 2009
0 views

Poetry Terminology

Indian Force
05. 05. 2009
0 views

Indian Force

Machine Intelligence
14. 05. 2009
0 views

Machine Intelligence

Data Link Layer
16. 05. 2009
0 views

Data Link Layer

Database Development Cycle
15. 05. 2009
0 views

Database Development Cycle

Queue
15. 05. 2009
0 views

Queue

Presentaion Skills
23. 04. 2009
0 views

Presentaion Skills

Network Layers
23. 05. 2009
0 views

Network Layers

Narmada Dam, India
23. 05. 2009
0 views

Narmada Dam, India

User Datagram Protocol
24. 05. 2009
0 views

User Datagram Protocol

Linear Momentum
28. 05. 2009
0 views

Linear Momentum

Stack and Queue
04. 06. 2009
0 views

Stack and Queue

Information Management
19. 06. 2009
0 views

Information Management

Role of Senior Management
19. 06. 2009
0 views

Role of Senior Management

Wake Up India
07. 06. 2009
0 views

Wake Up India

Adobe Flex 3.0
13. 06. 2009
0 views

Adobe Flex 3.0

Adobe Flex Presentation
13. 06. 2009
0 views

Adobe Flex Presentation

Introduction to Adobe Flex
13. 06. 2009
0 views

Introduction to Adobe Flex

Adobe Flash Media Server
13. 06. 2009
0 views

Adobe Flash Media Server

Dreamweaver
13. 06. 2009
0 views

Dreamweaver

Adobe Flash
13. 06. 2009
0 views

Adobe Flash

Flash CS4 Professional
13. 06. 2009
0 views

Flash CS4 Professional

Adobe Flash Lite
13. 06. 2009
0 views

Adobe Flash Lite

Digital Camera
13. 06. 2009
0 views

Digital Camera

Mozilla_Firefox
15. 06. 2009
0 views

Mozilla_Firefox

Managerial Accounting
27. 06. 2009
0 views

Managerial Accounting

Accounting  Information  System
01. 07. 2009
0 views

Accounting Information System

RETAILING AND MARKETING
06. 07. 2009
0 views

RETAILING AND MARKETING

ACCOUNTING IN BUSINESS
05. 07. 2009
0 views

ACCOUNTING IN BUSINESS

STRATEGIC RETAIL MANAGEMENT
05. 07. 2009
0 views

STRATEGIC RETAIL MANAGEMENT

Reiki
01. 08. 2009
0 views

Reiki

Using Buttons in PowerPoint
26. 04. 2009
0 views

Using Buttons in PowerPoint

Nanotechnology  for  Students
21. 08. 2009
0 views

Nanotechnology for Students

NANOSCIENCE
25. 08. 2009
0 views

NANOSCIENCE

Fundamentals of Nanoscience
27. 08. 2009
0 views

Fundamentals of Nanoscience

Nanoscience in Nature
27. 08. 2009
0 views

Nanoscience in Nature

Applied Mechanics
04. 09. 2009
0 views

Applied Mechanics

Accounts Payable Training
27. 06. 2009
0 views

Accounts Payable Training