Transcript Complexity
Complexity and Gödel
Incomplete theorem
電機三 B90901144
劉峰豪
Outline
Introduction to the idea of “complexity”
Complexity of some basic Operation
Problems
P and NP class
Gödel Incomplete Theorem
Introduction
Big O, small O…….are too trivial
Ln(r;c) for approximation of subexponential
time
P and NP class
Complexity of some Basic Operation
Given a,b
size a = |a| = ln a
+、-:
*:
/,%:
O(max(size a, size b))
O(size a * size b)
a=bq+r, O(size b * size q)
Ln
n is the input of a problem
O(e
c ((ln n ) r (ln ln n )1r )
Ln(r;c)=
Ln(0;c):linear O((ln n)c)
Ln(1;c):exponential O( nc)
)
Problems
Problem instance: a particular case of the
task
Search problem: it may have several correct
answers
Decision problem: answer yes or no
Some examples
Given N, and factor it
6=2*3
TSP
Does 91 have a factor between 2 and 63?
P and NP class
P
NP
NP-complete
Reduction of problems
Some applications in cryptography
P class
A decision problem p is in class P if there
exists a constant c and an algorithm such
that if an instance of p has input length <=n,
then the algorithm answers the question in
time O(nc)
Class NP
A decision problem p is in the class NP, if
given any instance of p, a person with
unlimited computing power can answer it
“yes”, and another person can verify it in time
P
P is in NP
Examples
Consider a graph G, is there a k-clique?
but no 5-clique
graph
4-clique
CLIQUE = {<G,k> | graph G has a k-clique}
Reducing one problem to another
Let p1 and p2 be 2 decision problems. We
say that p1 reduces to p2 if there exists an
algorithm that is polynomial time as a function
of the input length of p1 and that, given any
instance P1 of p1, constructs an instance P2
of p2 such that the answer for P1 is the same
as the answer in P2
Examples
P1:
input: a quadratic polynomial p(x) with integer
coefficients
Questions: does p(x) have two distinct roots?
P2:
input:an integer N
question: is N positive?
P1 reduces to P2
p1 < = p2
NP completeness
A problem p is NP-complete
if every other problem q in NP can be reduced to
P in polynomial time
p is in NP
P = NP ??
Relation between P and NPC??
Complexity and security of some
cryptosystem
DES:linear or differential
RSA:factorization ( quadratic sieve and
number field sieve )
quadratic sieve: (Ln(1/2;c))
number field sieve:(Ln(1/3;c))
ECC:exponential time
RSA-576 Factored
December 3, 2003
Number field sieve
Gödel Incomplete Theorem
Some Terms
Theorem
Effect
Some terms in Gödel Incomplete
Theorem
Consistent
Undecidable
Peano's Axioms
Answer Hilbert's 2nd Problem
Consistency
The absence of contradiction (i.e., the ability
to prove that a statement and its negative are
both true) in an Axiomatic system is known as
consistency.
true
A
B
false
undecidable
Not decidable as a result of being neither
formally provable nor unprovable.
A:”What B said is true.“
B:”What A said is false.“
Peano's Axioms
1. Zero is a number.
2. If a is a number, the successor of a is a number.
3. zero is not the successor of a number.
4. Two numbers of which the successors are
equal are themselves equal.
5. (induction axiom.) If a set S of numbers
contains zero and also the successor of every
number in S, then every number is in S.
Gödel Incomplete Theorem
All consistent axiomatic formulations of
number theory include undecidable
propositions
Any formal system that is interesting enough
to formulate its own consistency can prove its
own consistency iff it is inconsistent.
Conclusions
All formal mathematical systems have only
limited power.
We will never be able to have a system that
can prove all true statements about {0,1,2,…},
+, .
Note that this result predates that of Turing
and the solution of Hilbert’s polynomial
problem.
Effect
Turing: general recursive functions
John Von Neumann
AI