Is there a cryptographic solution to provide a “proof of exclusion”? I would like a proof that accomplishes the following:

$N$ strings are part of a set $S$.  There is a do_proof function on set $S$ that produces a succinct witness statement $P$.

$$P = \text{do_proof}(S)$$

For some new string $X$ that is not part of set $S$, I have some proof

$$\text{prove_not_a_member}(X, P) = \text{True}$$

that proves that $X$ is not a member of $S$. Assume that $S$ is large and $P$ is constrained in size.

I was thinking about aggregate signatures but I'm not sure. Basically I am looking for a way to succinctly prove non-membership.  It does not have to be zero-knowledge.

Is there a cryptographic solution to provide a “proof of exclusion”?
As shown recently$^1$ in [BBF], this can be carried out using universal accumulators [BdM].
Their construction is in the discrete-log setting in groups of unknown order (e.g., RSA group or class groups) and the size of both proofs of membership and non-membership is independent of the size of the set committed to. The security proof is in the generic group model under an &quot;adaptive root&quot; assumption. The main components of their construction is a hash function $H$ that maps strings to primes and a proof of exponentiation [W]. A long overview can be found in this blog-post. A shorter overview is given below.
Overview of the construction. Let's fix a group $G$ of prime order $p$ with a generator $g$. Loosely speaking, the value of the accumulator for a set $S$ is
$$\pi:=g^{\Pi_{s\in S}H(s)}.$$
To prove membership of an element $s^*$ in $S$, the prover gives out the co-factor, i.e., the product of all elements in $S$ except $s^*$:
$$\pi^*:=g^{\Pi_{s\in S\setminus\{s^*\}}H(s)}.$$
Given $\pi$ and $\pi^*$, the verifier simply checks whether $\pi=(\pi^*)^{H(s)}$.
Proving non-membership of an element $s^*$ in $S$ is trickier and requires an application of Bézout's identity that is due to Shamir [S]. Since $H$ maps elements to primes, with high probability $h^*=H(s^*)$ and $h=\Pi_{s\in S}H(s)$ will be co-prime and therefore there exists two numbers $a,b\in\mathbb{N}$ such that $ah^*+bh=1$. The proof now is $\pi^*:=(g^a,b)$ and the verifier checks whether
$$(g^a)^{h^*}\cdot\pi^b=g.$$
$^1$ The ideas were probably known before, but I couldn't find an earlier reference.
[BBF]: Boneh, Bünz and Fisch, Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, Crypto 19
[BdM]: Benaloh and de Mare, One-way Accumulators: A Decentralized Alternative to Digital  Signatures, Eurocrypt 93
[S]: Shamir, On the generation of cryptographically strong pseudorandom sequences., TOCS 83
[W]: Wesolowski, Efficient verifiable delay functions, Eurocrypt 19