Loading...
Please wait, while we are loading the content...
Similar Documents
Classification of recursive functions into polynomial and superpolynomial complexity classes
| Content Provider | Semantic Scholar |
|---|---|
| Author | Scḧurmann, Carsten Shah, Jatin |
| Copyright Year | 2005 |
| Abstract | We present a decidable yet incomplete criterion for classifying recursive functions into polynomial and superpolynomial complexity classes. We circumvent the usual necessity for encoding domains on Turing tapes by employing proof search for uniform derivations in a logic programming setting as the underlying model of computation. We reason about functions as relations and measure complexity in terms of the height of the derivation indexed by the size of the input. Our notion of complexity coincides with that characterized by Turing machines. This way, we can let functions range over first-order, higher-order, or dependently-typed domains and still examine their complexity in a meaningful way. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.itu.dk/people/carsten/papers/poly.pdf |
| Alternate Webpage(s) | http://www.itu.dk/~carsten/papers/csl05.pdf |
| Alternate Webpage(s) | http://cs-www.cs.yale.edu/homes/carsten/papers/poly.pdf |
| Alternate Webpage(s) | http://www.itu.dk/~carsten/papers/poly.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
