TeaserSince the problem is longish here is a special case that capture its essense.Problem: Let A be a detrministic algorithm for 3-SAT. Is the  problem of completely simulating the algorithm A (on every instance of  the problem). P-Space hard?(More precisely, are there reasons to believe this task is P-Space hard, does something in this direction follow from standard CC conjectures, and is there hope to prove that this task is X-hard for some complexity class X which is presumed to be strictly above NP.)Related questions: are-pspace-complete-problems-inherently-less-tractable-than-np-complete-problems;EDITED UPDATE: There are various interpretation for Completely simulating A. And there may be different interesting answers according to the interpretation. (Also Ryan Williams proposed an interpretation for simulating a non deterministic algorithm.) For a certain way to associate a decision problem to the computational task Completely simulate A, Joe Fitzsimons found an algorithm A for which this associated decision problem is still in NP. If completely simulate refers to being able to output the entire register of the computer at a given step $i$ then for Joe's algorithm it seems that $P^{NP}$ is what is needed. For this version (I think, but am not sure) Ryan's answer sketches a $P^{NP}$-hardness argument. Joe remarked that if of you are required to supply the entire registers (which is not any more a decision problem) it is not surptising that you need to step up and the complexity classes are not the same.   Anyway, if we require to output the state of the registers at a prescribed step $i$ then the answers of Ruan and Joe suggests (but again, I am not sure about it) that $NP^+$ is essentially $P^{NP}$. We can spaculate that by this interpretation the operation pushes up one step higher in the polynomial hiearachy, and that $PH^+ =PH$. In any case by these interpretations the answer to my teaser question is NO.  I had a more drastic interpretation for completely simulating an algorithm A in mind. (But perhaps Joe's and Ryan's interpretation is more interesting.) My interpretation by completely simulating algorithm A is that you outout the state of the registers at every step $i$. In particular, if the algorithm is not polynomial your output is also not polynomial. Under this drastic interpretation I wondered if we should believe that for every algorithm A, $C_A$ is P-SPACE hard, and what can we prove.Motivation:This question was motivated by a lecture by  Paul Goldberg (slides, video, paper) describing a paper with Papadimitriou and Savani. They showed that it P-space complete to find any equilibria that are computed by the Lemke-Howson algorithm. The problem to find some equilibrium point is only PPAD-complete. This gap is quite amazing and similar results are described already in Papadimitriu's well-known paper: The Complexity of the Parity Argument and Other Inefficient proofs of Existence (1991). (It is known that PPAD-complete problems cannot even be NP-hard (unless terrible things happen so this is far down in the complexity world compared to P-space).What the question is aboutMy question is about similar gaps for even older and more classical computational complexity problems. (Maybe this is already familiar.)Given a computational problem we can distinguish between three issuesa) Solve the problem algorithmicallyb) Reach the same solution as a specific algorithm Ac) Simulate the entire algorithm AOf course c) is at least as hard as b) which is at least as hard as a). The results mentioned above shows a gap between the computational difficulty of tasks a) and b) for the problem of computing equilibria. We would like to  understand the situation (and mainly the gap between a) and c)) for other computational problems. The question:The basic form of the question with an exampleWe start with a computational problem, Problem XAn example can beProblem X: Solve an instance of SAT with n variables we also specifyA: an algoritm that performs Problem Xand we pose a new problemProblem Y: Exactly simulate algorithm Aand we are interested in the computational difficulty of Problem Y. We wish to understand the class of such problems Y for all algorithms A that solve the original Problem X. Especially we want to know how easy can problem Y be (or how hard must it be) if we are allowd to choose the algorithm A at will. The proposed operation on complexity classesStart with a complexity class $C$ which is described by some computational task. Given an algorithm A to perform every instance of this computational task, consider a new complexity class $C_A$ which is described by the computational task of completly simulating $A$. Then we can (hopefully) define an ideal of complexity classes $C^+ = \{C_A:$ for all algorithms A}.If we let $P$ to describe whatever a digital computer can do in polynomial time (so I dont want to restrict attention e.g. to decision problems) then $P^+$ is the ideal spanned by $P$ itself.Finally, My QuestionsMy questions are: 1) Is the definition makes sense (in the wide sense of the word  sense). Is it well known or the same as (or similar to) some well  known thing. (My formulation was informal and in particular when we  move from specific problems like SAT to a complexity class like NP we  have to worry about various things that I neglected.)The next two questions assume that the definition can make sense or salvaged to make sense.2) Suppose we equip ourself with all the standard conjectures  regarding computational compleity. Can we say what $C^+$ is supposed  to be for some familiar complexity classes. (E.g. $C=NP$,  $C$=P-space,..)? EDIT: Several people pointed out that $PSPACE^+=PSPACE$. So > we can ask instead what is $(P^{NP})^+$? is $PH^+=PH$? Can we guess what are the compexity classes $C$ so that  $C^+$ is the ideal spanned by $C$?So the question how easy can the computational task of simulating an algorithm A for 3-SAT (when we can choose the algorithm to make it as easy as possible) is an interesting special case.3) Is there hope to actually prove something about this operation?Of course, if you prove that all complexity classes in $NP^+$ are P-space hard this will show that $P=NP$ implies $P=PSPACE$, which (I think) would be a huge and highly unexpected result. But if you show that all complexity classes in $NP^+$ are hard to somthing say in the third level of the polynomial Hieararchy (e.g. $\Delta_3^{\bf P}$) this would only imply things that we already know, things that follow from the fact that  $P=NP$ causes PH to collapse.
How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes
cc.complexity theory;big picture;structural complexity