Name
Abstract | ||
|---|---|---|
We develop theory concerning non-uniform complexity in a setting in which the notion of single-pass instruction sequence considered in program algebra is the central notion. We deflne counterparts of the complexity classes P=poly and NP=poly and formulate a counterpart of the complexity theoretic conjecture that NP 6µ P=poly. In addition, we deflne a notion of completeness for the counterpart of NP=poly using a non-uniform reducibility relation and formulate complexity hypotheses which concern restrictions on the instruction sequences used for compu- tation. We think that the theory developed opens up an additional way of investigating issues concerning non-uniform complexity. |
Year | Venue | Keywords |
|---|---|---|
2008 | Clinical Orthopaedics and Related Research | super-polynomial feature elimination complexity.,single-pass instruction sequence,non-uniform complexity,non-uniform super-polynomial complexity hypothesis,development theory,complexity class,computational complexity |
Field | DocType | Volume |
PH,Quantum complexity theory,Average-case complexity,Discrete mathematics,Combinatorics,Structural complexity theory,Sparse language,Descriptive complexity theory,UP,Complete,Mathematics | Journal | abs/0809.0 |
Citations | PageRank | References |
14 | 0.66 | 38 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jan A. Bergstra | 1 | 1946 | 240.42 |
| Cornelis A. Middelburg | 2 | 487 | 49.21 |