Instruction sequences and non-uniform complexity theory

Details Instruction sequences and non-uniform complexity theory Instruction sequences and non-uniform complexity theory

2008-09-02

arxiv.org/abs/0809.0352v3

Computer Science

Computational Complexity

31 pages; 31 pages, improvements of several proof outlines; 33 pages, presentation of section 7 improved

Scientific paper

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 define counterparts of the complexity classes P/poly and NP/poly and formulate a counterpart of the complexity theoretic conjecture that NP is not included in P/poly. In addition, we define 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 computation. We think that the theory developed opens up an additional way of investigating issues concerning non-uniform complexity.

Affiliated with

Also associated with

No associations

Rating

Instruction sequences and non-uniform complexity theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Instruction sequences and non-uniform complexity theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instruction sequences and non-uniform complexity theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-60684