Scribd Logo
Upload

Welcome to Scribd!

  • 67 views

    Algorithms For VLSI Design Automation: Chapter-4 Tractable and Intractable Problems

    Uploaded by

    kiranpani
    This chapter discusses tractable and intractable problems in the context of algorithms for VLSI design automation. It first covers combinatorial optimization problems and their decision versions. It then introduces NP-completeness and the consequences of this theory for CAD tool design. The chapter distinguishes between tractable problems that can be solved in polynomial time and intractable problems that cannot. It provides examples of tractable and intractable combinatorial optimization problems relevant to CAD tools, such as the satisfiability problem, Dijkstra's shortest path problem, and the traveling salesman problem.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd

    Algorithms For VLSI Design Automation: Chapter-4 Tractable and Intractable Problems

    Uploaded by

    kiranpani
    67 views6 pages
    This chapter discusses tractable and intractable problems in the context of algorithms for VLSI design automation. It first covers combinatorial optimization problems and their decision versions. It then introduces NP-completeness and the consequences of this theory for CAD tool design. The chapter distinguishes between tractable problems that can be solved in polynomial time and intractable problems that cannot. It provides examples of tractable and intractable combinatorial optimization problems relevant to CAD tools, such as the satisfiability problem, Dijkstra's shortest path problem, and the traveling salesman problem.

    Original Title

    chapter4_TractableAndIntractableProblems

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This chapter discusses tractable and intractable problems in the context of algorithms for VLSI design automation. It first covers combinatorial optimization problems and their decision versions. It then introduces NP-completeness and the consequences of this theory for CAD tool design. The chapter distinguishes between tractable problems that can be solved in polynomial time and intractable problems that cannot. It provides examples of tractable and intractable combinatorial optimization problems relevant to CAD tools, such as the satisfiability problem, Dijkstra's shortest path problem, and the traveling salesman problem.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    67 views6 pages

    Algorithms For VLSI Design Automation: Chapter-4 Tractable and Intractable Problems

    Uploaded by

    kiranpani
    This chapter discusses tractable and intractable problems in the context of algorithms for VLSI design automation. It first covers combinatorial optimization problems and their decision versions. It then introduces NP-completeness and the consequences of this theory for CAD tool design. The chapter distinguishes between tractable problems that can be solved in polynomial time and intractable problems that cannot. It provides examples of tractable and intractable combinatorial optimization problems relevant to CAD tools, such as the satisfiability problem, Dijkstra's shortest path problem, and the traveling salesman problem.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 6

    Algorithms

    for
    VLSI Design Automation

    Chapter-4
    Tractable And Intractable Problems
    Tractable And Intractable Problems
     What is covered in this chapter?
     Combinatorial Optimization problem and its decision version
     Then NP-Completeness is introduced
     Consequences of this theory for the design of CAD tools

     Tractable and Intractable Problems


     A Problem that can be solved in polynomial time is called tractable
    problem
    otherwise it is intractable problem
     It is feasible to use exact algorithms that find the optimal solution

    2
    Optimization Problem
     Problem:
     Problem refers to a general class
    eg: shortest path problem
     Instance:
     Instance refers to a specific case of a problem
    eg: shortest path problem between two gives vertices in a graph G
    An instance I = (F,c)
    where F is the feasible solutions and
    c is the cost function, assigning a cost value to each
    feasible solution
    c: F  R
    The solution of the optimization problem is the feasible solution with
    optimal cost (minimal/maximal)
    Optimization problem can be characterized by a finite set of
    variables
     Continuous optimization problem
     if the variables range over real numbers
     combinatorial optimization problem
     if the variables are discrete
     Most of the problems in CAD tools are combinatorial 3
    Optimization Problem Cntd.
     Examples of combinatorial problems
    Eg1: satisfiability problem

    Eg2: Dijkstra’s shortest-path problem


     selected edges can be given 1 and 0 for unselected edges

    Eg3: The Travelling Salesman Problem (TSP)

    4
    Optimization Problem Cntd.
    Eg4: The Travelling Salesman Problem (TSP)

    5
    Combinatorial
    Optimization Problem
     Problem:
     Problem refers to a general class
    eg: shortest path problem

     Instance:
     Instance refers to a specific case of a problem
    eg: shortest path problem between two gives vertices in a graph G

    An instance I = (F,c)
    where F is the feasible solutions and
    c is the cost function, assigning a cost value to each
    feasible solution
    c: F  R
    The solution of the optimization problem is the feasible solution
    with optimal cost (minimal/maximal)

    You might also like