Algorithm Complexity and Performance

Bart Massey

Example: The Triangle Problem

        PROBLEM TRIANGLE

        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

• 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

Example: BEST TENTMATES

        PROBLEM BEST TENTMATES
        [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.

BEST TENTMATES is NPC

• 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.