Algorithm Complexity and Performance

Algorithm Complexity and Performance

Bart Massey

Example: The Triangle Problem


        Given: An undirected graph G=(V, E).

        Question: Is there a "triangle" in G, that is, a set T of
                  vertices {v[1], v[2], v[3]} in V s.t. all pairs
                  of vertices in T are edges in E.

The Assumptions Of Big-O

  • The big-O of an algorithm is independent of the machine it is implemented on.

  • The scaling at sizes of interest is the big-O scaling.

  • At least some representative instances scale like big-O.

  • Lower-order factors don't matter.

  • Roughly, f(n) in O(n^k) is tractable, others are not.

Polytime and NP

  • Difficulty of problem vs complexity of algorithm

  • Roughly, f(n) in O(n^k) is tractable, others are not.

  • Some problems are clearly exponential, for example enumerating integers of size n.

Is it polynomial?

  • For some algorithms it's not so obvious whether in O(n^k).
    • Consider a problem like NUMBER PARTITIONING: given a set of positive integers with even sum, partition it into two subsets such that the sum of each subset is equal.
    • Clearly can guess a right answer and quickly check it: O(|S||max e|).
    • But is there an algorithm? No one knows.


  • NP = Nondeterministic Polynomial: class where guess and check works in polytime

    • P=NP? Fundamental CS question
    • In practice, assume NP=EXP
    • But may solve many large instances with some work
  • Examples:

    • SAT
    • Many production scheduling problems
    • Rubik's cube and other puzzles

C Completeness

  • P is C Complete = P is in C + P is C Hard

  • P is C Hard = can "reduce" any problem P' in C to P

  • Reduction: Show that for every instance p' of P', you can

    • transform p' into an instance p of P
    • use a P-solver to find a solution s of p
    • transform s to a solution s' of p'.

Proving A Problem Is NP-Complete

  • SAT is in NP: Cook/Karp/Levin ca 1971

  • Long lists of other NPC problems reduced to SAT, e.g. Garey and Johnson

  • If you have to do it yourself

    • First show that your problem P is in NP: usually easy
    • Next, find an existing NPC problem P' that's "close"
    • Finally, do the reduction


        [deriv. MATES by Dennis Sasha, Dr. Dobbs Journal August 1998]

        Given: A tent of capacity n. A set P of campers.
               A symmetric preference function f : P x P -> {0,1}
               indicating which campers "like each other". A
               constant h.

        Find: A subset P' of P, with |P| <= n, such that
              sum(f(c, c') | c, c' in P') is >= h. Everyone
              else sleeps outside.


  • Is BEST TENTMATES in NP? Yes, guess and check

    • But notice the funny way we rigged the problem
    • This is implicitly a maximization: Why? Binary search
  • Is BEST TENTMATES NP-hard? Yes, by reduction from k-CLIQUE

    • Instance of k-CLIQUE is a graph and a k.
    • We rig f(v1,v2) = 1 if there is an edge from v1 to v2 and 0 otherwise. Now we build a tent of capacity k and set h = k(k-1)/2.
    • Solve BEST TENTMATES instance: if the answer is yes, then the set of vertices in the tent is your k-CLIQUE

Final Thoughts

  • Easy to get reduction backwards, with disastrous results

  • Why do we care? Because it's easy to waste a lot of time trying to find an efficient algorithm for an NP-hard problem.

    • For example, Prof. Singh low-power routing problem
  • Most (all?) of the algorithms we will study in this course are in P. Bleah.

Last modified: Tuesday, 15 April 2014, 3:49 PM