Lecture 26: Final Review Session 2 (Open Q&A) - CSCI 381 Goldberg

Administrative Updates

Today (May 6) - Review Session 2: Open Q&A session - students may ask about any topic: material, quizzes, keywords, or exam format. This is the second and final review session before the final exams.
Grades: All assignments should be graded before Monday, May 11. Students should know all their grades (except the final exam results) before the exams begin.
May 18: CUNY First lists May 18th as a date, but no virtual classroom will be held. If there is enough interest, the professor may post an optional lecture; in terms of semester material, the course is now complete.

Final Exam Details

The types of questions are similar to what has been seen in prior quizzes, but it will likely be more difficult. In prior quizzes multiple choice was provided, but on the final exam short answer responses may instead be required.

Final Exam - Part 1 (Keyword Exam): Monday, May 11, during the same time slot used for quizzes earlier in the semester.
- Students may need to supply the exact term definition from the lecture notes, rather than using multiple choice.
- All keywords are found in the lecture notes. Whatever is in the lecture notes is the official standard — external sources may differ.
Final Exam - Part 2 (Cumulative Material): Wednesday, May 13, during the same time slot used for quizzes earlier in the semester.
- Students may need to provide an explanation of how they arrived at their answer — not just the answer itself.
- Do not use the Brightspace virtual classroom on May 13 (the professor attempted to remove it but encountered an error; a note “do not use” was added to it).

Karp 21 and Nondeterminism

Karp 21 was discussed in the lectures on Feb 18, Mar 2, 4, 9. These March lectures used the same notes file.

The issue is that of nondeterminism, a theoretical concept that enables a machine to make guaranteed correct decisions when the program calls for it. (The latter point is critical: a nondeterministic program/computer must use the options to it. The analogy I gave in lecture was the write-in vote during an actual election for a TV character of a President Jed Bartlet (West Wing). That perhaps would be free will but it would not be nondeterminism. The former allows one to create new options not presented, the latter cannot. The nondeterministic computer MUST choose from the options presented to it.)

As fantastic as nondeterminism is, Turing already proved that the deterministic computer could accomplish the same thing, just not as efficiently. So, the added factor of nondeterminism does not affect Solvability (Effectiveness), but rather Complexity (Efficiency). Nondeterminism makes the choice in $O(1)$ constant time. Deterministic computers will probably need much more time for the same choices.

Colloquially, it is stated that time complexity on a deterministic computer is governed by the number of steps, whereas time complexity on a nondeterministic computer is governed by the number of decisions it makes.

P and NP

So, Cook and Karp where both inspired by a comment that a colleague Jack Edmonds made distinguishing hard and easy problems based on whether or not the time complexity is polynomial or exponential (or worse). From there, two classes of problems were defined: P and NP.

$P$ = the set of all problems that can be solved (algorithms) in a polynomial amount of time using a deterministic computer.
$NP$ = the set of all problems that can be solved (algorithms) in a polynomial amount of time using a nondeterministic computer.

To this end, Dijkstra suggested to view this distinction from a programming perspective. (Dijkstra articulated this perspective much later, but it captures the essence of the issue.) Nondeterministic programming is at its core identical to Deterministic programming but in addition has this one extra command:

Choose x from {….} such that P(x) is true.    //Satisfiability

This extra command is essentially satisfiability at its core - which is precisely why Cook was thinking of satisfiability when formulating his work. Note that while Dijkstra’s formulation allows $x$ to be any type (as in discrete math, where inputs to a Boolean predicate could be anything), the technical definition in Cook and Karp’s papers specifies $x$ as Boolean. In essence, however, they are the same concept.

So, the question Karp formulated was $P = NP$ ?

Now, even if the answer to this famous problem (with its 1 million dollar prize at the Clay institute) was Yes, (which most scientists believe is not so) that may not have any practical application for us (cf. Hartmanis suggestion that complexity should be determined by practical considerations, not theroretical ones) because $n^{100}$ is still polynomial. In this regard, an exponential algorithm applied to a small data set could outrun a different polynomial solution to the same problem because there may be constants that prolong the practical amount of time that the polynomial algorithm requires (cf. Gargantuan or Cosmic Constant). At some point, a polynomial could generate a number larger than the number of molecules in the universe, in which case a computer could not process it — there would simply not be enough physical material to store such a value. If on the other hand, the answer to $P = NP$ is NO (and most believe so), this will not affect solvability per se (similar to a discussion above).

Cook, Karp, and Levin

Cook, Karp and Levin were all interested in demonstrating certain problems to be Np-hard/complete. They all did this using a concept called reduction but in their own research contexts found the necessity to give a (slightly) different definition.

Cook (1971) was trying to prove that all Np-complete problems reduce to Satisfiability. As such, reduction was one-way process.
Karp (1972) extended Cook’s work and tried to show that 20 specific problems can be iteratively (ie a chain of) problems reduced from Satisfiability. Since Cook already showed that these (ie ALL) such problems reduce to Satisfiability, Karp then defined reduction as a two-way process; it is just that Cook already proved one of those two directions and that is why in Karp’s paper only one direction is specified.
Levin (1973) was concerned by the governing extra constraint necessary for reductions within the $P = NP$ question: $\leq_p$ — that small " $p$ " at the foot of the reduction icon ( $\leq_p$ ; some use oc notation instead, which visually resembles an infinity symbol rotated on its side) stresses the fact that the “cost of doing business” cannot exceed (here) polynomial amount of time. This can be thought of the amount of time it will take for the first problem to translate/absorb/adapt the extra information provided by the second problem to solve the problem. Remember that in reduction the Parent problem reduces to the Child problem but it is the Child problem that solves the Parent problem, BUT at what cost? The reason this polynomial cost constraint is critical is: if the cost were to exceed polynomial, then problem $A$ cannot actually make use of problem $B$ ‘s information within the $P = NP$ framework — it would require an exponential step inside what is supposed to be a polynomial reduction, which defeats the purpose entirely. As such, Levin defines reduction in terms of finding the “extra” piece of information (and its cost) that the first problem needs from the second problem in order to solve its own problem. This extra piece of information can be called a certificate/witness/signature.

Karp towards the beginning of the paper (pages 89-90) provides very specific polynomial time deterministic algorithms that are similar to some of the nondeterministic problems defined later in the paper. This was to show that small “tweaks” (changes in parameters) could change a P problem to a NP problem or vice versa. (case by case situation)

Sometimes changing 2 to 3 will change P to NP, but that does not mean it will always be so.
Sometimes changing edges to vertices will change P to NP, but that too does not mean it will always be so. (For example, KARP#7 and KARP#8, Feedback Node Set and Feedback Arc Set.)
Changing directed to undirected did not change NP to P (in the case of KARP#9 and KARP#10 un/directed hamiltonian circuits (cycles)) but may cause such a change elsewhere.

Knapsack (KARP#18)

Defined as follows:

A luggage (knapsack) has a maximum weight constraint $b$ .
One is traveling and therefore can only take a certain amount of items with her/him. (I guess an exception would be made for Hermione’s knapsack.)
An inventory of $n$ $n$ items termed $A_i$ $A_{i}$ is placed in front of you and you must determine which items you can take that will reach the maximum weight constraint.
- NOTE: In reality when traveling, the traveler is only concerned that the total weight is $\leq b$ , but in Karp’s problem it has to $= b$ . A possible practical scenario would be traveling overseas where it is to the advantage of the traveler that as many items as possible come with them since that will make their travel generally easier.
$X_i$ $X_{i}$ will state whether or not item $A_i$ $A_{i}$ was packed into the knapsack: $X_i = 1$ $X_{i} = 1$ means it was; $X_i = 0$ $X_{i} = 0$ means it was not.
- NOTE: There is technically a little oversimplification here that mathematicians will mostly allow: Technically the item $A_i$ and its weight should be two separate Variables but here we are using them interchangeably. A more precise formulation would define a weighting function $W$ such that $W(A_i) = W_i$ , keeping the item and its weight as distinct entities.
So that the goal equation is:

\sum_{i=1}^{n} A_i \cdot X_i = b

What is interesting about this problem is that so many variants have been proposed, some of which are actually in P. For example, Fractional Knapsack where if the entire item would cause the weight limit to be broken, one could fix that by only taking a fraction of that item. Spices are a typical example in the literature for this. As noted above, we are generally interest in $\leq b$ BUT Karp defines it as $= b$ .

Purpose of the Encodings

The purpose of the various encodings that Godel (mainly) and other provided was utilized by theoreticians all to deal with the following problem: Standard recursion, which is based on standard (weak) induction, can only access one previous level’s output and start from one base case. But, we know that there are many standard mathematical functions that require multiples of each:

Function	Encodings	Note
Fibonacci	Pairing Functions, Polynomial Encoding, Godel Combinatoric Encoding	Defined on two inputs
All Recurrence Relations	Godel Length Encoding, Godel Prime Encoding, Godel Beta Encoding, Chowla Combinatoric Encoding	Defined on any number of inputs

At a concrete level: the Pairing Function, Polynomial Encoding, and Godel Combinatoric Encoding each encode two numbers into a single number, while Godel Length Encoding and Godel Prime Encoding each encode any number of numbers into a single number.

Note: Any of these encodings with some effort can be used to encode either situation. The listing here is what it was primarily used for.

Davis shows that by using the above encodings one can rewrite recursive mathematical functions that are defined by having more than one base case and/or requiring more than one previous levels’ output by an encoded version of this function which will only require one base case and access to only one previous level’s output. As such all the above will still work with a standard (simple) recursion process.

The historical significance of this reduction to simple recursion is connected to the goals of Turing and his colleagues in the 1920s and 30s. Working without any computers yet built, they sought to mathematically prove the minimum amount of work that would be needed to construct one — an early form of reduced instruction set computing (RISC). By establishing that complex recursive functions could be reduced to the simplest possible form, they gave themselves a better shot at eventually building a working machine.