Opened 8 years ago

Last modified 8 years ago

#38 assigned article

paper in Nature

Reported by: xkovar3 Owned by: xkovar3
Priority: minor Milestone:
Component: publications Keywords:
Cc: Due Date:


with Pary

Is the P vs NP an important question?


  • 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


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

Change History (1)

comment:1 Changed 8 years ago by xkovar3

Owner: set to xkovar3
Status: newassigned
Note: See TracTickets for help on using tickets.