[FrontPage] [TitleIndex] [WordIndex

Author: Chris Murphy

Note: We spent a large portion of time at the beginning of class handling questions about Problem 5 on the written problem set before moving onto new material. The question and notes are replicated to some extent below, but were discussed more in a Q+A format than as a specific set of new information. The problem is replicated for reference at the bottom of the first section.

The Infamous Problem Five

A Review

Recall on a previous exam a question about building a queue from two stacks: smoke and mirrors. The goal was to determine how to enqueue and dequeue items using only stack operations. The type of thinking that went into solving that problem could prove useful to solving problem 5.

Question from Katie Rivard:

Answer from Lynn:

Comment from Sarah Zwicker:

The Actual Problem

Suppose that someone gives you a polynomial-time algorithm to decide formula satisfiability (i.e., given a propositional logic formula, is there some truth assignment that makes it true or does no such truth assignment exist?). Describe how to use this algorithm to find satisyfing assignments -- i.e., to identify one such truth assignment -- in polynomial time.



A K-clique is a completely connected subgraph of a larger graph. For instance, the graph below has a K-clique of size 3 (several, actually), as well as a K-clique of size 4. It does not have a K-clique of size 5 (A 5-Clique). The problem of finding a given sized clique in a graph is NP-Complete.

|\   /|\
| \ / | \
|  X  |  o
| / \ | / 
|/   \|/


If we have a formula in Conjunctive Normal Form (CNF), in triplets (3-CNF). Deciding whether a given formula is satisfiable (known as the 3-SAT problem) is also NP-Complete.

Rhetorical Question: If we are given a magic bullet which can solve the k-clique problem, can we solve 3-SAT as well?

Answer: Of Course!

Assume we have the 3-CNF equation (X v Y v Z) ^ (A v X v X!) ^ (E v Y! v Z) ^ (Z! v Q v X) where X! is 'X-bar'. We begin by laying out the graph as shown below:

    Z!    Q     X    
X                   E
Y                   Y!
Z                   Z
  A      X     X!    

Essentially, you take each triplet in the 3-CNF notation, and start by simply grouping them as sides of a polygon shaped graph. Next, connect everything which is NOT from the same side of the polygon (ie - the same triplet) and which also does NOT directly conflict (for instance, don't connect X to X!). This is a serious amount of lines. I have attempted to draw in all the lines which connect to the top-left X node -- I realize it's sorta cluttered. You would repeat this process for each node in the graph.

    Z!    Q     X    
  / /-----/ /---/             
X<---/-----/   -----E
Y | \\\-------------Y!
  | | \                
  |  \ \----\               
Z |   \      \------Z
  |    \-|                
  A      X     X!    

The Punchline

If a 4-clique exists, we have solved the 3-SAT problem. If we find a 4-clique in our graph, we must have 4 independent clauses that are true (one in each triplet) and which don't contradict.

What We Did This Semester

The work we did this semester can be divided into three topics:

Example Topic

The below diagram shows what areas of CS topics associated with SWOOGLE, the Semantic Web Google, would fall into.

       Algorithms                       Automata                      Programming Languages
     Stacks     Trees (and Traversal)         Parsing(Grammar)  |         PROLOG+LISP
 Hash Table     Queue               Regular Expressions   /             Propositional Logic
     Arrays    Order statistics        Graphs           /         Predicate Calculus
       Sorting (n log n)     Finite State Machines    /           Turing Machines
                                                    /    lambda Calculus      Computability
THETA(1) THETA(log n)   THETA(n)    Tractable   ------->    NP - Expensive! Intractable

Note that lambda Calculus is the formalism behind Lisp - we did not talk about it under the name "lambda calculus".


Wikipedia was used extensively for supporting documentation - it is linked from the sections where appropriate.

2013-07-17 10:43