id summary reporter owner description type status priority milestone component resolution keywords cc due_date
38 paper in Nature xkovar3 xkovar3 "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(n^k) for k<=2, sometimes k<=1]
- in many P-NP discussion, O(n^100) is mentioned not be a feasible
complexity
but is O(n^3) or O(n^2) 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=10^7, -> n^2 = 10^14
- 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 -> n^2)
Practical Solutions of NP (Complete) Problems
- probabilistic, heuristic
- příklady
Discussion/Conclusion
* P does not mean practical
* if P=NP - one NP complete is in P (even O(n^2))
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))
" article assigned minor publications