Paper Info

Title | ||
---|---|---|

Instruction sequences and non-uniform complexity theory |

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 |

Authors (2 rows)

Cited by (14 rows)

References (38 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Jan A. Bergstra | 1 | 1946 | 240.42 |

Cornelis A. Middelburg | 2 | 487 | 49.21 |