Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computabiltiy theory, I asked:

we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we treat these programs/functions/algorithms as just computable functions. The question is, when the function operates on an input to produce an output, can we consider the operation of function as using only a number of arithmetic operations (addition, subtraction, multiplication and division) on an input? Or does the use of if/else make the aforementioned not true? If this is true, is the number of arithmetic operations polynomially proportional to the lowest time complexity bound possible for solving a problem? (That is, if the lowest time complexity is $\text{O(whatever)}$, then the number of arithmetic operations is $\text{O(whatever)}^k$ where $k$ is some rational number.)

I learned an answer to this, and now I would like to present variation: If we limit our scope to programs that can be modeled as operations of arithmetic operations on inputs, can these program be simulated by a machine that can only do basic arithmetic processes on inputs (multiplciation, division, subtraction, addition) with polynomial overhead (That is, if the lowest time complexity is $\text{O(whatever)}$, then the number of arithmetic operations is $\text{O(whatever}^k)$ where $k$ is some rational number.) to the lowest possible time complexity for solving a problem?

share|improve this question
    
still no comments? Is this a hard question? –  logica Apr 22 '13 at 6:31
    
Cross-posted at mathoverflow.net/questions/128343 –  logica Apr 22 '13 at 12:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.