Name
Abstract | ||
|---|---|---|
We present an approach to non-uniform complexity in which single-pass instruction sequences play a key part, and answer various questions that arise from this approach. We introduce several kinds of non-uniform complexity classes. One kind includes a counterpart of the well-known non-uniform complexity class P/poly and another kind includes a counterpart of the well-known non-uniform complexity class NP/poly. Moreover, we introduce a general notion of completeness for the non-uniform complexity classes of the latter kind. We also formulate a counterpart of the well-known complexity theoretic conjecture that NP not subset of P/poly. We think that the presented approach opens up an additional way of investigating issues concerning non-uniform complexity. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.7561/SACS.2014.1.47 | SCIENTIFIC ANNALS OF COMPUTER SCIENCE |
Keywords | DocType | Volume |
non-uniform complexity class, single-pass instruction sequence, projective Boolean function family | Journal | 24 |
Issue | ISSN | Citations |
1 | 1843-8121 | 8 |
PageRank | References | Authors |
0.86 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jan A. Bergstra | 1 | 1946 | 240.42 |
| Cornelis A. Middelburg | 2 | 487 | 49.21 |