Bounded computation and incompleteness

Is there a complete theory T over a logical language L such that bounded computation may be encoded in it? Computational questions can be framed as arithmetical ones by interpreting them over natural numbers. Let $\phi$ be a first order statement which states that $P \neq NP$ in the language of arithmetic. Then either $\phi$ belongs to Th(N) or its negation does (i.e.) it contains the answer to the P vs NP problem.

However, since Th(N) is not RE, I would like to know if computation (in particular, bounded computation) can be interpreted over some alternate structure with nicer properties (i.e. whose theory is decidable). Note that if a theory is complete, then it cannot be RE-complete (i.e.) deciding whether any $\phi$ belongs to the theory is not RE-complete, it is either recursive or RE-hard.

The context is Razborov's paper on "Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic" in which he shows that the bounded arithmetic theory $S_2^2(\alpha)$ cannot prove polynomial circuit lower bounds for SAT assuming Strong Pseudo Random Generators (SPRGs) exist. Here the statement "SAT does not have poly size circuits" can be written as a bounded sentence when interpreted over the naturals.

I want to understand if the presence of a total order is required for the interpretation of computation inside a structure. Suppose I take graphs with the minor ordering (which is a WQO), is it possible to interpret computation inside this? My only point of reference is the undecidability of First order satisfiability by reduction from the Halting Problem. In this case, we do not seem to require a successor function, just the idea of a "future" configuration with certain properties. I understand that this setting is different from interpretation inside a structure. I want to understand this difference.

• the Presburger arithmetic (N,0,+) is complete, and many works deal with the complexity of solving specific problems in this setting. – Denis Sep 5 '13 at 11:04
• Please note that I am not interested in arithmetic. Presburger is not strong enough and adding multiplication gives incompleteness. I am looking for an alternate structure. I am also not interested in bounded arithmetic (work by Parikh, Buss etc) – Thinniyam Srinivasan Ramanatha Sep 5 '13 at 12:47
• What do you mean Th(N) is incomplete?! Th(N) is a complete theory. You still need to further clarify the question and what you are looking for. Explain what you mean by "P vs. NP over other structures", what do you mean by "nicer structures", and how is this to Sasha's paper. Sasha's paper simply says that we cannot prove a separation of P from NP in a particular theory (which is a rather weak theory) assuming the existence of SPRNGs. – Kaveh Sep 7 '13 at 6:22
• This still needs cleaning up. I still don't see how Sasha's paper is related to the rest of the question. You are stating lots of things in this question without explaining how they are related to your question. I think you need to think and formulate your question clearly, otherwise you will continue to introduce new phrases without defining them and make the question more confusing. Don't through phrases, be precise as much as possible. Check the tips for writing a better question in help center. – Kaveh Sep 7 '13 at 18:21
• In your last edit, what do you mean by "the presence of total order inside a structure"? Do you mean a total order for elements in the structure is definable in the language of the structure? (think carefully before answering and don't change it after you answer, and if you don't know then how would you expect us to answer the question?). ps: The edits you are making makes me feel that you don't know what you want to ask, just have some vague ideas, i.e. it is not an issue of writing but not having spent time to formulate your question. – Kaveh Sep 7 '13 at 18:24

P vs. NP can be studied for other structures, first order logic with order is sufficient to phrase the question whether every $\Sigma^b_1$ formula is equivalent to a quantifier-free one (and you can enrich the language to contain all operations that you want to assume to be efficient). The strings case is old (I will add reference later). It is also studied over real numbers (in the context of BSS model).