paper in Nature

[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¹⁴
• 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²⁾

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²⁾⁾

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))