Name
Abstract | ||
|---|---|---|
The computational complexity of bounded sets of the two-dimensional plane is studied in the discrete computational model. We introduce four notions of polynomial-time computable sets in R$^2$ and study their relationship. The computational complexity of the winding number problem, membership problem, distance problem, and area problem is characterized by the relations between discrete complexity classes of the NP theory. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1137/S009753979325456X | SIAM J. Comput. |
Keywords | Field | DocType |
bounded set,discrete computational model,number problem,two-dimensional regions,discrete complexity class,np theory,computational complexity,polynomial-time computable set,membership problem,distance problem,area problem,computer model,winding number,complexity class,polynomial time | Average-case complexity,Discrete mathematics,Asymptotic computational complexity,Computational problem,Structural complexity theory,Combinatorics,Counting problem,Function problem,Complete,Mathematics,Computational resource | Journal |
Volume | Issue | ISSN |
24 | 5 | 0097-5397 |
Citations | PageRank | References |
22 | 2.94 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arthur W. Chou | 1 | 41 | 6.26 |
| Ker-I Ko | 2 | 196 | 28.54 |