Opened 7 years ago
Last modified 7 years ago
#38 assigned article
paper in Nature
Reported by: | xkovar3 | Owned by: | xkovar3 |
---|---|---|---|
Priority: | minor | Milestone: | |
Component: | publications | Keywords: | |
Cc: | Due Date: |
Description
with Pary
Is the P vs NP an important question?
Introduction
- definice: P - v poly vypočtu, NP - v poly ověřím
- P vs NP one of the most important problem in computer science
- P ~ prakticky řešitelný
- NP ~ neřešitelný
- příklady z učebnic, soutěže, nejcitovanější práce, zejména
uvádějící praktický dopad
(bezpečnost na tom staví)
- we show that P vs NP question is not important from any practical point
Practicability/Scalability? of Computing
- is any P-algorithm practical? [only O(nk) for k<=2, sometimes k<=1]
- in many P-NP discussion, O(n100) is mentioned not be a feasible
complexity
but is O(n3) or O(n2) OK?
- It depends on the size of our problems
- Does it depend on the MB or GB of data to process?
- Only partially, it also depend on the size of one item Ex: 10 MPx picture -> n=107, -> n2 = 1014
- Price of one operation
- CPU instruction - fast
2GB of RAM, scanning of the whole RAM (CRC) = seconds??
- going out of main memory - order of magnitude slower
--> memory boundary
- Moore's law - the difference is growing
NP Completeness
- reducibility of one problem to other, reduction alg in P
- usually the size is growing in P, going out of memory
- příklady: - složitosti
+ změna velikosti (n -> n2)
Practical Solutions of NP (Complete) Problems
- probabilistic, heuristic
- příklady
- P does not mean practical
- if P=NP - one NP complete is in P (even O(n2))
then all NP problems are in P but due to non-linear reduction they
are not practical
- many NP problems are solvable in practise because of problem reformulation
(not best solution but good enough, additional limits on input
(metrics for distances))
Note: See
TracTickets for help on using
tickets.