Transcript ComputationalComplex.. - Computer Science & Engineering

Themes of Presentations
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Rule-based systems/expert systems (Catie)
Software Engineering (Khansiri)
Fuzzy Logic (Mark)
Configuration Systems (Sudhan)
* Tutoring and Help Systems (Nicolas)
Design (Liam)
* Help-Desk Systems (Denis)
* Experience/case Maintenance (Fabiana)
Markov Decision Processes (Megan)
Reinforcement learning (Megan)
e-commerce (Joe)
* Recommender systems (Chad)
* Conversational case-based reasoning (Shruti)
* Semantic web and CBR (Steve)
Computational Complexity
CSE 335/435
Why Studying Computational
Complexity in IDSS?
•We will observe that some techniques seem ideal to
provide decision support
•We will formulate those techniques as computational
problems
•Many of these problems will turn out to be intractable
(NP-complete or worse)
•Thus, we will study relaxations that approximate
solutions. These relaxations are in P.
A Quick Overview of
Computational Complexity
•What does the notation O(f) indicates
•When do we say that a program has polynomial complexity
•What does it mean that a problem is P?, in NP?
•What does it mean that a problem is NP-complete?
Definition
O(g) = { f : lim n  f(n)/g(n) is a real number}
For example:
what functions are in O(x3)?
 x3
 x3 + 2X + 3
 x2 log x
 7
 6x3 - 1000
…
Functions not in O(x3)?
 x4
 x10 + 2X + 3
 x3 log x
 7x
 …
Complexity: O-notation
Search (e: element, A[]: array)
i1
While (A [i]  e and i < N+1)
i  i +1
Return i
Worst case:
k(N+1), where k = time for making the
comparison A [i]  e
This algorithm’s complexity is lineal (i.e., O(N))
Comparison of Problems /
Solutions by Their Complexity
•All the other sorts
O(N2)
•MST •Shortest path O(N log N )
•Search in unordered array
O(N )
O(log N)
•Binary search ordered array
• all the other sorts:
O(1)
•Simple instruction
•Search in complete Binary
Search Trees
•Heapsort
•Quicksort
P
Deterministic Computation
(Informal)
Key questions: if a computer is confronted with a certain state
of the computation where a choice must be made,
1. are all the alternatives transitions known?, and
2. given some input data, is it known which transition the
machine will make?
Input data
“current state”
“transition”
“new state”
If the answer to both of these
questions is “yes”, the computation
is said to be deterministic
Nondeterministic Computation
If the answer to any of these questions is “no”, the
computation is said to be nondeterministic
That is, either
• some transitions are unknown, or
• given some input data, the machine can make more
than one transition
P versus NP
P is the class of problems that can be solved in O(Nk), where
k is some constant by a deterministic computer
O(N)
DeterministicSearch (e: element, A[]: array)
i1
While (A [i]  e and i < N+1)
i  i +1
Return i
NP is the class of problems that can be solved in O(Nk),
where k is some constant by a nondeterministic computer
O(1)
Non-determinisitcSearch(e: element, A[]: Array)
i  Oracle(e, A)
return i
NP Complexity (I)
Homework:
why 1 implies
2 and why 3
implies 2?
How to proof that a problem prob is in NP:
1. Show that prob is in P, or
2. Write a program solving prob using the oracle that
runs in polynomial time, or
Most books
3. Write 2 polynomial programs that: (1) generate a
possible solution S and (2) tests if S is a solution to
prob
NP Complexity (II)
The class NP consists of all problems that can be solved
in polynomial time by nondeterministic computers
NP Include all problems in P
The key question is are there problems in NP that are not in P
or is P = NP?
We don’t know the answer to the previous question
But there are a particular kind of problems, the NP-complete
problems, for which all known deterministic algorithms have
an exponential complexity
Some Problems Seem Too Hard
(NP-Complete)
•SAT
•Circuit-SAT
P
•Vertex Cover
•TSP
NP
NP-Complete
A problem prob is NP-complete if:
• prob is in NP
• Every other problem nprob in NP can be reduced in
polynomial time into prob.
Reduction:
nprob
Polynomial
transformation
solution
prob
Conjunctive Normal Form
A conjunctive normal form (CNF) is a Boolean expression
consisting of one or more disjunctive formulas connected by an
AND symbol (). A disjunctive formula is a collection of one or
more (positive and negative) literals connected by an OR
symbol ().
Example:
(a)  (¬ a  ¬b  c  d)  (¬c  ¬d)  (¬d)
Problem (CNF-problem): Given a CNF form obtain
Boolean assignments that make form true
Example (above):
a  true, b  false, c  true, d  false
Decision problem
Homework: Proof
that CNF-SAT is in
NP (use definition
3 of Slide 11)
`Decision problem: problem with YES/NO answer
•Decision problems can be easier than the standard variant
•But for proving NP-completeness they facilitate the proofs
Problem (CNF-problem): Given a CNF form obtain
Boolean assignments that make form true
Problem (CNF-SAT): Given a CNF form, is there an
assignment of the variables that makes the formula true?
Cook Theorem (1971):The CNF-SAT is NP-complete
Illustration of NP-Completeness of
CNF-SAT
We will show that the problem of determining if an element e is
contained in an array A can be reduced to CNF-sat
Solution: The following CNF formula is true if and only if e
is in A:
(A[1] = e  A[2] = e  …  A[n] = e)
Traversing A to obtain this formula can be done in O(N)
(Vague) Idea of The Proof (I)
State1: S1
State2: S2
Computer Memory
S2
S1
S1
S2
Program
…
<instruction>
….
A computation: S1, S2, S3, …, Sm
(Vague) Idea of The Proof (II)
Statej
Computer Memory
Sj
Sj
Program
…
<instruction>
….
Sj can be represented as a logic formula Fj
The computation can be represented S1, S2, S3, …, Sm as
(F1  F2  …  Fm), which is transformed into a CNF
How to proof that A Problem is NPComplete
We want to proof that prob is NP complete.
This is done in two steps:
1. Show that prob is in NP
2. Show that a known NP-complete (e.g., CNF-sat)
problem can be reduced (polynomial) into prob
nprob
Polynomial
transformation
solution
CNFsat
Polynomial
transformation
solution
prob
Circuit-sat (I)
A Boolean combinatorial circuit consists of one or more
Boolean components connected by wires such that there is
one connected component (i.e., there are no separate parts)
and the circuit has only one output. Boolean components:
x
y
x
y
x
xy
xy
¬x
Circuit-sat (II)
Circuit-problem: Given a Boolean combinatorial circuit,
find a Boolean assignment of the circuit’s input such that the
output is true
x
y
z
Circuit-SAT: Given a Boolean combinatorial circuit, is
there a Boolean assignment of the circuit’s input such that
the output is true
Homework
1. Obtain an algorithm (pseudo-code) solving the Circuit-SAT
2. Explain why your solution is not polynomial
3. Prove that Circuit-Sat is NP complete:
a) Show that Circuit-SAT is in NP
b) Prove that CNF-SAT can be reduced into Circuit-SAT:
(a)  (¬a  ¬b  c  d)  (¬c  ¬d)  (¬d)
•Show a circuit representing the above formula
•Describe an algorithm for this transformation
•Explain why this algorithm is in P