Please enable JavaScript.

Coggle requires JavaScript to display documents.

M15 - Coggle Diagram

- - - - we can think about problems that can be solved in polynomial time as the set that computer science theoreticians call P. A more formal definition includes in P only decision problems, which are problems with yes/no answers.
        
        Hamiltonian circuit problem
        
        Determine whether a given graph has a Hamiltonian circuit—a path that starts and ends at the same vertex and passes through all the other vertices exactly once.
        
        Traveling salesman problem
        
        Find the shortest tour through n cities with known positive integer distances between them (find the shortest Hamiltonian circuit in a complete graph with positive integer weights).
        
        Knapsack problem
        
        Find the most valuable subset of n items of given positive integer weights and values that fit into a knapsack of a given positive integer capacity
        
        Partition problem
        
        Given n positive integers, determine whether it is possible to partition them into two disjoint subsets with the same sum.
        
        Bin-packing problem
        
        Given n items whose sizes are positive rational numbers not larger than 1, put them into the smallest number of bins of size 1.
        
        Graph-coloring problem
        
        For a given graph, find its chromatic number, which is the smallest number of colors that need to be assigned to the graph’s vertices so that no two adjacent vertices are assigned the same color.
        
        Integer linear programming problem
        
        Find the maximum (or minimum) value of a linear function of several integer-valued variables subject to a finite set of constraints in the form of linear equalities and inequalities.
    - - Informally, an NP-complete problem is a problem in NP that is as difficult as any other problem in this class because, by definition, any other problem in NP can be reduced to it in polynomial time