A classical challenge in complexity theory and cryptography is to simulate interactive proof systems by non-interactive proof systems. In this work we leverage approaches from recent works in derandomization to address this challenge, focusing on non-interactive simulations that are sound against uniform adversarial algorithms.

Our results concern fundamental questions in complexity theory, such as the \mathcal{NP} vs \mathcal{PSPACE} question, and also in cryptography, such as the question of constructing non-interactive zero-knowledge arguments for \mathcal{NP} from unstructured assumptions. Relying on strong complexity-theoretic hardness assumptions (that will be described below):

1. *Complexity theory.* We prove that \mathcal{PSPACE} is contained in the ``computationally sound'' version of \mathcal{NP}. Specifically, for every L\in\mathcal{PSPACE}, membership in L can be verified by an \mathcal{NP}-type (deterministic, polynomial-time) verifier V with the following guarantee: The verifier accepts every x\in L when given a proof \pi from an honest prover that runs in fixed exponential time T_P; and every uniform adversary running in probabilistic time \mathrm{poly}(T_P) cannot find x\notin L and \pi such that V(x,\pi)=1, except with negligible probability in T_P. As a corollary in the area of bounded arithmetic, under the same assumptions, we deduce that \mathcal{NP}\ne\mathcal{PSPACE} is not provable in the theory {APC}_1. This is a strong theory, which captures many of the major results in complexity.

2. *Cryptography.* We construct new cryptographic protocols, including succinct non-interactive arguments ({SNARG}s) for \mathcal{NC} in the plain model, as well as non-interactive zero-knowledge and witness indistinguishable ({NIZK} and {NIWI}) proof systems for \mathcal{NP}, all with computational soundness against uniform adversaries. The {SNARG} relies solely on the aforementioned complexity-theoretic assumption, whereas the {NIZK} and {NIWI} require also a sub-exponentially secure one-way function (which should be injective in the case of the {NIWI}). These are the first constructions of the above protocols that do not rely on highly structured cryptographic primitives.

Roughly speaking, following Chen and Tell (FOCS 2021, STOC 2023), the complexity-theoretic hardness assumptions throughout our paper assert the existence of functions f \colon \{0,1\}^n \to \{0,1\}^k that are computable in polynomial time and hard for bounded-space machines (say, linear space) in a strong average-case sense: No efficient algorithm can find an input x on which the bounded-space machine computes f, except with negligible probability.

Very minor changes, incorporating two reviewer comments.

A classical challenge in complexity theory and cryptography is to simulate interactive proof systems by non-interactive proof systems. In this work we leverage approaches from recent works in derandomization to address this challenge, focusing on non-interactive simulations that are sound against uniform adversarial algorithms.

Our results concern fundamental questions in complexity theory, such as the \mathcal{NP} vs \mathcal{PSPACE} question, and also in cryptography, such as the question of constructing non-interactive zero-knowledge arguments for \mathcal{NP} from unstructured assumptions. Relying on strong complexity-theoretic hardness assumptions (that will be described below):

1. *Complexity theory.* We prove that \mathcal{PSPACE} is contained in the ``computationally sound'' version of \mathcal{NP}. Specifically, for every L\in\mathcal{PSPACE}, membership in L can be verified by an \mathcal{NP}-type (deterministic, polynomial-time) verifier V with the following guarantee: The verifier accepts every x\in L when given a proof \pi from an honest prover that runs in fixed exponential time T_P; and every uniform adversary running in probabilistic time \mathrm{poly}(T_P) cannot find x\notin L and \pi such that V(x,\pi)=1, except with negligible probability in T_P. As a corollary in the area of bounded arithmetic, under the same assumptions, we deduce that \mathcal{NP}\ne\mathcal{PSPACE} is not provable in the theory {APC}_1. This is a strong theory, which captures many of the major results in complexity.

2. *Cryptography.* We construct new cryptographic protocols, including succinct non-interactive arguments ({SNARG}s) for \mathcal{NC} in the plain model, as well as non-interactive zero-knowledge and witness indistinguishable ({NIZK} and {NIWI}) proof systems for \mathcal{NP}, all with computational soundness against uniform adversaries. The {SNARG} relies solely on the aforementioned complexity-theoretic assumption, whereas the {NIZK} and {NIWI} require also a sub-exponentially secure one-way function (which should be injective in the case of the {NIWI}). These are the first constructions of the above protocols that do not rely on highly structured cryptographic primitives.

Roughly speaking, following Chen and Tell (FOCS 2021, STOC 2023), the complexity-theoretic hardness assumptions throughout our paper assert the existence of functions f \colon \{0,1\}^n \to \{0,1\}^k that are computable in polynomial time and hard for bounded-space machines (say, linear space) in a strong average-case sense: No efficient algorithm can find an input x on which the bounded-space machine computes f, except with negligible probability.