Session 2: �Tractable and Intractable problems: P and NP Class problems, NP completeness, Satisfiability problem.

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

Tractable Problems - Definition

• Definition: Tractable problems are those that can be solved efficiently, meaning there exists an algorithm that solves them within a polynomial amount of time, O(n^k).
• Polynomial Time (P): Explain that problems solvable in polynomial time are generally considered feasible or “easy” to compute.
• Significance of P: Mention that the class P represents a foundational class in computational complexity.

Examples of Tractable Problems

• Sorting Algorithms: QuickSort and MergeSort are examples of algorithms that solve sorting problems in polynomial time.
• Shortest Path Problem: Algorithms like Dijkstra’s for finding the shortest path in graphs are tractable.
• Binary Search: Finding an element in a sorted array, solvable in logarithmic time, is a basic tractable problem.

Amity School of Engineering & Technology

Intractable Problems - Definition

• Definition: Intractable problems are those that cannot be solved efficiently; they require exponential or super-polynomial time, making them impractical for large inputs.
• Exponential Time Complexity: Explain that intractable problems often require O(2^n)or greater, which is not feasible for large inputs.
• Distinction from Unsolvable Problems: Emphasize that while intractable problems can theoretically be solved, unsolvable problems cannot be computed at all.

Examples of Intractable Problems

• Subset Sum Problem: Given a set of integers, determining if a subset sums to a particular number is intractable for large inputs.
• Traveling Salesman Problem (TSP): Finding the shortest route to visit a set of cities, a classic example of an NP-hard problem.
• Knapsack Problem: Choosing items with maximum value without exceeding weight limits is computationally intensive and intractable for large datasets.

Amity School of Engineering & Technology

P and NP Class problems, NP completeness

Amity School of Engineering & Technology

Introduction to Complexity Classes

• Definition of Complexity Classes: Explain that complexity classes categorize problems based on the resources needed for computation, primarily time and space.
• Focus on Time Complexity: Mention that this presentation will emphasize time complexity, crucial for defining P, NP, and NP-complete problems.
• Importance of Understanding Complexity Classes: Briefly introduce why these classes matter in assessing which problems can be feasibly solved.

Amity School of Engineering & Technology

Amity School of Engineering & Technology

What is the P Class?

• Definition of P: P represents the class of problems that can be solved in polynomial time by a deterministic Turing machine.
• Formal Notation: Define P as the set of decision problems solvable by an algorithm in O(n^k) time, where k is a constant and n is the input size.
• Significance of Polynomial Time: Explain that polynomial time complexity is often considered “tractable” or feasible in practical computation.

Examples of P Class Problems

• Sorting Problems: Algorithms like QuickSort, MergeSort, solvable in polynomial time.
• Shortest Path in Graphs: Dijkstra’s algorithm, which finds the shortest path in O(n^2) time for dense graphs.
• Binary Search: Search problems in a sorted array, solvable in logarithmic time.

Amity School of Engineering & Technology

What is the NP Class?

• Definition of NP: NP is the class of problems for which a solution can be verified in polynomial time by a deterministic Turing machine.
• Key Idea - Verification vs. Solution: Explain that while we may not know how to solve the problem in polynomial time, we can verify a given solution efficiently.
• Examples of Verification: If provided a potential solution (e.g., a specific path in TSP), we can check it in polynomial time.

Examples of NP Class Problems

• Traveling Salesman Problem (TSP): Given a set of cities, finding the shortest route to visit each city once and return.
• Knapsack Problem: Maximizing the total value of items without exceeding weight capacity.
• Subset Sum Problem: Determining if there exists a subset of numbers that adds up to a specified sum.

Amity School of Engineering & Technology

Reducibility

• a problem Q can be reduced to another problem Q’ if any instance of Q can be “easily rephrased” as an instance of Q’, the solution to which provides a solution to the instance of Q
• Is a linear equation reducible to a quadratic equation?
• Sure! Let coefficient of the square term be 0

Amity School of Engineering & Technology

NP - hard

• What are the hardest problems in NP?

​

​

• That notation means that L₁ is reducible in polynomial time to L₂ .
• The less than symbol basically means that the time taken to solve L₁ is no worse that a polynomial factor away from the time taken to solve L₂.
• A problem (a language) is said to NP-hard if every problem in NP can be poly time reduced to it.

​

Amity School of Engineering & Technology

NP-Completeness

​

• Definition of NP-Complete Problems: NP-complete problems are the hardest problems within NP. If an NP-complete problem can be solved in polynomial time, then all NP problems can.
• Properties of NP-Complete Problems:
• They are in NP.
• Every NP problem can be reduced to any NP-complete problem in polynomial time.
• Significance: NP-complete problems serve as a benchmark for intractability in NP.

Amity School of Engineering & Technology

Common NP-Complete Problems

• Satisfiability Problem (SAT): Deciding if a Boolean expression can be made true by assigning appropriate truth values.
• Traveling Salesman Problem (TSP): Finding the shortest path that visits each city once and returns to the start.
• Knapsack Problem: Selecting items to maximize value without exceeding capacity.
• Graph Coloring: Determining the minimum number of colors needed to color a graph without adjacent vertices sharing the same color.

Amity School of Engineering & Technology

Satisfiability problem

Amity School of Engineering & Technology

Introduction to the Satisfiability Problem

• Definition: The Satisfiability (SAT) problem asks if there exists an assignment of values (true/false) to variables in a Boolean formula that makes the formula evaluate to true.
• Importance in Computation: Introduce the SAT problem as a fundamental problem in computational complexity

Boolean Logic and Expressions

• Boolean Variables and Operators: Define Boolean variables, AND, OR, NOT, and their roles in logical expressions.
• Example of a Boolean Expression: Illustrate a simple Boolean formula, e.g., (A∨B)∧(¬A∨C).
• Goal of Satisfiability: Explain that the objective is to determine if there exists a truth assignment for A, B, and C that makes this expression true.

Amity School of Engineering & Technology

Formal Definition of the SAT Problem

• Instance of SAT: Define a SAT instance as a set of variables and a logical formula composed of clauses in conjunctive normal form (CNF).
• Solution (Satisfying Assignment): Explain that a solution to SAT is any assignment of values that makes the entire formula true.

Conjunctive Normal Form (CNF)

• Definition of CNF: Explain CNF as a form where the formula is a conjunction (AND) of clauses, each clause being a disjunction (OR) of literals.
• Conversion to CNF: Mention that any Boolean formula can be converted into CNF, often used in SAT problems.
• Example: Provide an example of a CNF formula, e.g., (A∨B)∧(¬A∨C)∧(B∨¬C).

Amity School of Engineering & Technology

Types of SAT Problems

• 1-SAT: Every clause has one literal. Explain that this is trivially solvable.
• 2-SAT: Each clause has two literals. Mention that 2-SAT is solvable in polynomial time.
• 3-SAT: Each clause has three literals. Explain that 3-SAT is NP-complete, and this version is typically what is referred to in the context of SAT complexity.

Examples of SAT and 3-SAT Problems

• 3-SAT Example Problem: Provide an example like (A∨B∨¬C)∧(¬A∨C∨D)∧(B∨¬D∨E).
• Assignment Solution: Demonstrate a potential solution by showing a truth assignment that satisfies all clauses.

Amity School of Engineering & Technology

Applications of the Satisfiability Problem

• Logic and Circuit Design: Ensuring that digital circuits work correctly by verifying that certain conditions hold.
• AI and Machine Learning: SAT problems in constraint satisfaction and decision-making.
• Cryptography: Explain how SAT helps in testing cryptographic algorithms’ resilience.
• Scheduling and Planning: Use cases in logistics where SAT solves scheduling, resource allocation, and planning problems.

Amity School of Engineering & Technology