Never mind how efficiently you can compute it, can you compute it at all?
MWF 9:30 - 10:20
Colloquium
“The Single Distance Problem”
Dr. Michael Bennett (Geneseo math alum, Ph. D f/ UR(?), now at RIT)
Wednesday, Nov. 4, 2:45, Newton 204
Extra credit as usual
Exam 2
Thursday
Material since 1st exam, e.g., trivial lower bounds, adversary arguments,
decision trees, basic complexity classes, etc.
Section 8.1 plus additional material from classes
Rules and format otherwise similar to 1st exam, especially open
references, closed person. But maybe more detailed questions
Questions?
The Class P
Chapter 34 introduction and section 34.1
Definitions of classes
P = solvable in polynomial time
NP = verifiable in polynomial time, may not be solvable in poly time
NP complete = subclass of NP
If any member solvable in poly time all of NP is
The open problem in computer science: is P = NP?
Methods for proving membership in classes
Reduction: show how to turn instances of problem A into
instance of B in poly time, solve B in poly time, thus conclude A is in P
Similarly for NP, etc.
Encoding?
Need well-defined notion of input size
Does size vary acording to how you write input?
Consider adding 2 numbers
Abstractly: input = numbers x, y
Calculator: input = string of decimal digits
Size = number of digits, logarithmically smaller than x, y
Encoding = syntax rule for writing inputs
Decision vs optimization problems
NP (and other classes) defined in terms of decision problems
Example: searching unordered list of letters
Input
List of letters f/ alphabet, encoded as ##,##,##,##,##/
Letter represented as 2-digit number
Letter to seek, encoded as ##
e.g., complete input might be ##,##,##,##/##
Intuitively, size = n = length of list
Encoded size = 3n + 2 in Θ(n)
…which is generally what you hope, encoding doesn’t change input
size appreciably and analyses can be done in terms of an intuitive measure of size
Decision problem: “is this input in some set that I am deciding?”
In this case the set is that set of strings in which the section before “\”
contains at least one occurrence of the section after “\”
The problem with numbers
Fixed-size encoding -> finite set of numbers but encoding doesn’t
alter size measure
Variable-size encoding -> any number representable in any way can be an
input, but input size might depend on values of numbers, arithmetic no longer constant time
A problem that might seem to be in P but (probably) isn’t: factoring
arbitrary-size naturals
Input: natural number, n
Output: non-trivial factor of n or 0 if n is prime
Simple algorithm:
for i = 1 to ceiling of sqrt(n)
if n mod i = 0
return i
end of for
return 0
Time seems to be Θ(√n)
(And is, but n isn’t a valid measure of input size here)
But input needs to be encoded as variable-size string of base-10 digits