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

### 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(n
^{k) for k<=2, sometimes k<=1] }- in many P-NP discussion, O(n
^{100) is mentioned not be a feasible }

- in many P-NP discussion, O(n

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 }

- Only partially, it also depend on the size of one item
Ex: 10 MPx picture -> n=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

^{2) }

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

**Note:**See TracTickets for help on using tickets.