Lecture 16: Quiz Review 2 - CSCI 381 Goldberg

Administrative Updates

• Quiz Review Session: Today’s lecture focuses on reviewing key topics for the upcoming quiz
• Quiz Topics:
  • CARP’s 21 NP-complete problems
  • P = NP problem and non-determinism
  • Primitive recursive functions and their definitions
  • Bounded and unbounded minimization
  • Reduction techniques and components
• Spring Break: Discussion of minimization and further topics will continue in a future class after spring break
• Course Materials: Instructor will email complete notes (Excel sheet or link) with full transcript of today’s review session
• Verification Note: Understanding how to verify solutions is critical (e.g., how to verify feedback node/arc sets without computing all cycles)
• Quiz Date: Monday after spring break
• Optional Keywords Quiz: Monday, March 30 (during class time on Brightspace)

Optional Keywords Quiz Details

An optional quiz on keywords will be held during class time on Monday, March 30 on Brightspace under Quizzes. This quiz addresses student requests to better understand how keywords are selected and tested on the final exam (which weights keywords at 50%).

About the Quiz: The instructor will email an alphabetical list of all keywords discussed through the first half of the semester. The quiz will consist solely of multiple-choice questions about these keywords.

What “Optional” Means: The syllabus assigns 30% of the total grade to three regularly scheduled quizzes. The “optional” status works as follows:

• The instructor will compute the quiz average two ways: (1) excluding this keywords quiz, and (2) including this keywords quiz
• The higher of these two averages will be multiplied by 30% toward the semester total
• If you do not take the quiz, it does not affect your grade
• If you take the quiz but score lower than your other quiz averages, it does not affect your grade
• If you score higher on the keywords quiz than your regular quizzes, your quiz average increases accordingly

Syllabus Topics on Quiz (Elaborated)

KARP’s Paper (1972, but still very relevant today)

• Non-determinism

• $P = NP$ problem

• KARP presents (and we elaborated in the notes) tweaked problems that are in $P$ with similar problems in $NP$

• Cook’s Satisfiability (1971)

• KARP’s 21 (1972) = 20 + 1

  The lecture notes grouped these problems based on application and/or mathematical structure needed for the definition of the problem.

Reduction Definitions and Components

• Three definitions for reduction (Cook, Karp, Levin)
• Components of reduction when applied to the Reduction Tree p.96 of Karp’s paper

KARP’s 21 Problems: Detailed Discussion

Problems Dealing with Cycles

Feedback Node Set and Feedback Arc Set (Problems 7 and 8)

Both problems require identifying a set of elements that intersect all cycles in a graph:

• Feedback Node Set: Find a minimal set of vertices such that every cycle in the graph contains at least one vertex from this set
• Feedback Arc Set: Find a minimal set of edges such that every cycle in the graph contains at least one edge from this set

The key insight is that while the definition requires knowing all cycles (which is computationally expensive), verification is tractable. If given a proposed feedback set, you can verify it by deleting those elements from the graph and checking if the resulting graph is acyclic, which can be done in polynomial time using depth-first search, breadth-first search, or topological sorting.

Hamiltonian Circuit (Problems 9 and 10: Directed and Undirected)

• Definition: Find a single cycle that visits every vertex of the original graph exactly once
• Directed Hamiltonian Circuit: The graph has directional edges
• Undirected Hamiltonian Circuit: The graph is bidirectional

The term “circuit” historically meant cycle (e.g., circuit courts traveled in cycles between towns). KARP was careful to define both directed and undirected versions because small changes to problem definitions can change difficulty from easy to hard or vice versa (see page 89-90 of KARP’s paper).

Problems Dealing with Packing

Set Packing (Problem 4)

Given a collection of sets that have already been created, select a maximum number of mutually exclusive sets (sets with no common elements).

Set Covering (Problem 6)

Given a collection of sets, find the minimum number of sets whose union covers all elements.

Exact Cover (Problem 14)

Find a collection of mutually exclusive sets whose union covers all elements exactly once (combining the constraints of both set packing and set covering).

Knapsack (Problem 18)

Select items to maximize total value without exceeding a weight limit. Unlike the packing problems above, knapsack requires selecting from items that have not yet been packed, trying to fit as many valuable items as possible within the weight constraint.

Problems Dealing with Partitioning

Partition (Problem 20)

Divide elements into two groups such that the sum of values in each group is equal.

Max Cut (Problem 21)

Divide the vertices of a graph into two groups, then find the partition that maximizes the total weight of edges between (not within) the groups. This is important in network theory, such as identifying the most vulnerable set of network cables in a communication system.

Chromatic Number (Problem 11)

Color the vertices of a graph using $K$ colors such that no two adjacent vertices share the same color. This is a $K$-partition problem where vertices are grouped by color.

P Versions of NP-Hard Problems

For many of KARP’s NP-hard problems, slightly modified versions are in P:

• Fractional Knapsack (P): When items can be partially taken (like pouring out some spice), the problem becomes tractable
• Bipartite Matching (P): The 2D version of 3D matching, where points have only X and Y coordinates
• Edge Cover (P): The P-version of vertex cover; find edges whose endpoints cover all vertices
• 2-Coloring (Bipartite Coloring) (P): Chromatic number when limited to 2 colors
• Linear Programming (P): The continuous version of 0-1 integer programming, where variables can take real values instead of just 0 or 1

Primitive Recursion

PR/Class (the latter part being a broader more inclusive version of primitive recursion, as below):

Davis is trying to formulate a RISC approach to mathematically model all computable functions. 25 different mathematical functions defined (Davis does more than this especially with prime numbers and encodings which we will discuss in a future class) but for now only these 25 PR functions were necessary for our discussion.

Leading upto Bounded Minimization

Ackermann’s function was used to prove that primitive recursive cannot model all computable functions.

What Davis realizes is that a version of minimization is what is missing from the formulation of primitive recursive to cover/implement all computable functions.

Unbounded Minimization vs. Bounded Minimization

Unbounded Minimization is the technique missing from the PR formulation and it is not the simple initial functions NSU that are lacking another initial function, but rather another technique is missing in order to achieve all possible computable functions.

Bounded Minimization (Primitive Recursive) finds the first time (index/input) that a predicate is true over a range of numbers (bound). This range limitation is too restrictive for defining all computable functions. If we drop the range and ask for the first time (ever) that the predicate is true, then all computable functions can be derived from PR definition plus adding in the unbounded minimization.

An issue can arise because how do we know ahead of time that an arbitrary predicate is true anywhere. This further leads Davis to realize that not only does PR definition plus unbounded minimization yield a definition for all computable functions, this also yields a definition for all partially computable functions. The partially computable function can go through an infinite loop for some possible input.

If one were to mathematically model this partially computable function based on the expanded notion of PR, which includes unbounded minimization (again, Davis calls this version a PRC = Primitive Recursive Class), then will correspond to a mathematical/functional definition of all partially computable functions.

This PRC definition for partially computable includes an unbounded minimization which may/not actually achieve a true value (that is equivalent to the infinite loop that the partially computable function experiences.) If one could guarantee that the unbounded minimization always halts (i.e. the predicate does have at least on set of inputs that the predicate is true on) then, this PRC approach will yield all computable functions.

Summary

• NSU with composition and recursion produces all primitive recursive functions and does not produce all computable functions (cf. Ackermann’s) (and this is the case even with bounded minimization)
• NSU with composition and recursion and unbounded minimization where/if it is guaranteed that the boolean predicate has a true value for some input, will produce all computable functions.
• NSU with composition and recursion and unbounded minimization where/if it is not guaranteed that the boolean predicate has a true value for some input, will produce all partially computable functions.