Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Can all programs be modeled as operations of elementary arithmetic operations on inputs? and computability 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 (multiplication, 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|cite|improve this question
    
still no comments? Is this a hard question? – logica Apr 22 '13 at 6:31
1  
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.