Loading...
Please wait, while we are loading the content...
Similar Documents
P versus NP question
| Content Provider | Semantic Scholar |
|---|---|
| Author | Wisniewski, D. |
| Copyright Year | 2006 |
| Abstract | Many important problems like 3-SAT, Clique, Vertex cover, Travelling Salesman’s problem, etc. have only exponential time solutions. It means that in practice they cannot be solved efficiently except with small input sizes. The P versus NP question asks whether the problems can be solved in polynomial time or whether they are intractable by their nature. To outline the P versus NP problem more clearly, let us consider as an example the Travelling Salesman’s problem (TSP). A generic instance of TSP consists of a finite set C = {c1, c2, ..., cm} of cities and distances d(ci, cj) ∈ Z for each pair of cities ci, cj ∈ C, where i, j ∈ {1, 2, ...,m} and i 6= j. A solution to the problem is a sequence (cΠ(1), cΠ(2), ..., cΠ(m)) of cities from C such that it minimizes the following cost function: ∑m−1 i=1 d(cΠ(i), cΠ(i+1)) + d(cΠ(m), cΠ(1)) |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.joensuu.fi/pages/whamalai/sciwri/dominik.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
