Transcript Complexity

Agenda
• Blog signup…
• First week impressions
– High School vs. University..
• Career Night
• CS outcomes
• Complexity
First Week Impressions?
•
•
•
•
How was your first week at ASU?
Good things?
Frustrating things?
Differences from High School?
Career Exploration Night
Thursday September 8th
• Mark your calendars for a special evening event (approx.
5:30-8:00PM) in the Memorial Union (on ASU Tempe Campus)
• At the event, you will have the opportunity to talk to working
engineers from a variety of industries and companies, to find
out more about engineering careers. You will have the chance
to ask them anything you want to know about including what
it’s like to be an engineer, or what you need to do to be
successful.
• Attendance will be taken;
– there will be no class that week (no class on 9th September)
• More information to come later
“Algorithms and Complexity”
Sorting…
• When is a sequence in sorted
order?
– How many pairwise comparisons do
I need to do to check if a sequence
of n-numbers is sorted?
– If I have a procedure for checking
whether a sequence is sorted, is it
reasonable to sort a sequence of
numbers by generating
permutations and testing if any of
them are sorted?
Intelligence is putting the
“test” part of
Generate&Test
into generate part…
Exactly when do we say an algorithm is
“slow”?
• We kind of felt that O(N! * N) is a bit much
complexity
• How about O(N2)? O(N10)? Where do we draw the
line?
– Meet the Computer Scientist Nightmare
– So “Polynomial” ~ “easy” & “exponential” ~ “hard”
– 2n eventually overtakes any nk however large k is..
• How do we know if a problem is “really” hard to solve
or it is just that I am dumb and didn’t know how to do
better?
– If checking the correctness of the solution itself takes
more than polynomial time, then we know the problem
must be hard..
– But there are many problems, for which checking the
correctness is polynomial, and yet we don’t know any
efficient algorithm
n
2
Tower of Hanoi (or Brahma)
• Shift the disks from the left
peg to the right peg
– You can lift one disk at a
time
– You can use the middle
peg to “park” disks
– You can never ever have a
larger disk on top of a
smaller disk (or KABOOM)
• How many moves to solve
a 2-disk version? A 3-disk
one? An n-disk one?
– How long does it take (in
terms of input size), to
check if you have a
correct solution?
Career Exploration Night Experience
Topics for Group Discussion:
– Share the majors, job titles, and companies of the
individuals you met.
– What was the most important thing you learned about
engineering?
• Most surprising?
• Most interesting?
– What kind of projects/work activities were mentioned?
– What differences did you find between “real people” and
what you had read beforehand? Similarities?
– What was the best advice that you received?
Discussion Highlights
(Group reporting)
• What was the most important thing you learned?
– Most surprising?
– Most interesting?
• Major differences/similarities between information from
‘real people’ and information you read?
• Types of projects/work activities? Did you see different
job functions within a single discipline (or similar job
functions across multiple disciplines)?
• What was the best advice that you received?
Job Title: ___________________________
Company Requires Or Desires
My Qualification
Difference Between The Two
What I Am Going To Do To Make Up The
Difference or Gain a Measurable
Accomplishment
Classes P and NP
Class P
• If a problem can be solved
in time polynomial in the
size of the input it is
considered an “easy”
problem
– Note that your failure to solve
a problem in polynomial time
doesn’t mean it is not
polynomial (you could come
up with O(N* N!) algorithm
for sorting, after all 
Class NP
• Technically “if a problem can
be solved in polynomial time
by a non-deterministic turing
machine, then it is in class NP”
• Informally, if you can check the
correctness of a solution in
polynomial time, then it is in
class NP
– Are there problems where even
checking the solution is hard?
How to explain to your boss as to why
your program is so slow…
I can't find an efficient algorithm, I guess I'm just too dumb.
I can't find an efficient algorithm,
because no such algorithm is possible.
I can't find an efficient algorithm, but neither
can all these famous people.
The P=NP question
• Clearly, all polynomial problems
are also NP problems
• Do we know for sure that there
are NP problems that are not
polynomial?
• If we assume this, then we are
assuming P != NP
• If P = NP, then some smarter
person can still solve a problem
that we thought can’t be solved
in polytime
– Can imply more than a loss of
face… For example, factorization
is known to be an NP-Complete
problem; and forms the basis for
all of cryptography.. If P=NP, then
all the cryptography standards
can be broken!
NP-Complete: “hardest” problems
in class NP [the giants of NP-world]
EVERY problem in class NP can
be reduced to an NP-Complete
problem in polynomial time
--So you can solve that problem
by using an algorithm that solves
the NP-complete problem
Reducing Problems…
Mathematician
reduces “mattress
on fire” problem
Make Rao Happy
General NPproblem
Make Everyone in
ASU Happy
Boolean
Satisfiability
Problem
3-SAT
Make Little
Tommy Happy
Make his entire
family happy
Academic Integrity
• What it means
• Typical ASU policy
– Homeworks
– Exams
• Take-Home Exams
– Term papers
Scholarship Opportunities
• General Scholarships
• The FURI program
• NSF REU program
Is exponential complexity the worst?
2n
• After all, we can have 22
More fundamental question:
Can every computational
problem be solved in finite
time?
“Decidability”
--Unfortunately not
guaranteed  [and Hilbert
turns in his grave]
Some Decidability Challenges
• In First Order Logic, inference
(proving theorems) is semi-decidable
– If the theorem is true, you can show
that in finite time; if it is false you may
never be able to show it
• In First Order Logic + Peano
Arithmatic, inference is undecidable
– There may be theorems that are true
but you can’t prove them [Godel]
Practical Implications of Intractability
• A class of problems is said to
be NP-hard as long as the
class contains at least one
instance that will take
exponential time..
• What if 99% of the instances
are actually easy to solved?
--Where then are the wild
things?
Satisfiability problem
• Given a set of propositions P1 P2 … Pn
• ..and a set of “clauses” that the propositions must
satisfy
– Clauses are of the form P1 V P7 VP9 V P12 V ~P35
– Size of a clause is the number of propositions it
mentions; size can be anywhere from 1 to n
• Find a T/F assignment to the propositions that respects
all clauses
• Is it in class NP? How many “potential” solutions?
Canonical NP-Complete Problem.
• 3-SAT is where all clauses are of length 3
Example of a SAT problem
• P,Q,R are propositions
• Clauses
– P V ~Q V R
– Q V ~R V ~P
• Is P=False, Q=True, R=False as solution?
• Is Boolean SAT in NP?
Hardness of 3-sat as a function of
#clauses/#variables
This is what
happens!
You would
expect this
p=0.5
~4.3
#clauses/#variables
Probability that
there is a satisfying
assignment
Cost of solving
(either by finding
a solution or showing
there ain’t one)
Phase Transition!
Theoretically we only know that phase transition ratio
occurs between 3.26 and 4.596.
Experimentally, it seems to be close to 4.3
(We also have a proof that 3-SAT has sharp threshold)
Phase Transition in SAT