Question: Somewhere around the 3rd year of my physics PhD. program I came into this amazing subject of complexity theory. May be a motivating factor was that I was digging in my spare-time into this physics/complexity interface. Anyhow I took up courses in complexity theory and a few associated regions in the CS theory department in my university and I started attending one of the group meetings there and tried to contribute to a project (sadly the project turned out to be very hard and didn't move enough) 

But how do I actually go about finding a career in this subject? 
Either in academia or industry? 

I won't be taken seriously if I make a regular CS PhD. application because my background has no overlap with an usual CS grad student and neither am I interested in CS per se. (like I found the graduate "algorithms" course extremely boring though the mathematical algorithms part was fascinating where they did stuff like LP, SDP, entropy extraction, pseudorandomness etc.) My interest is complexity theory and its interface with physics : which I see as a fascinating branch of mathematics! (and I do have quite a strong background in mathematics)

Answer: 
In a mathematics paper or thesis, the most common practice is simply to include all proofs in the body of the document, each one immediately following the statement of its corresponding theorem or lemma. So you should seriously consider just doing that.

Placing proofs in an appendix might be appropriate if they are really ancillary to the main thrust of your thesis. For instance, maybe there is a result that is not really relevant to the rest of the thesis, but you've included it simply because it is interesting. Or you state a result that is well known, but you have written your own proof as an exercise. Or you have multiple proofs of the same statement; you might want to place one of them in the body, and move the other(s) to the appendices.

But in any case, I would think there would not be more than a few proofs that would fit these criteria. As such, it would be most natural to place each proof in its own appendix, rather than to group them by body chapter or any other criterion.

You could give the appendices names like "Appendix A. Proof of Theorem 1.2.3". Or better yet, something more descriptive like "Appendix A. Proof of the Snargleberg–Veeblefester Theorem (Theorem 1.2.3)". Of course, you will want to use LaTeX's `\ref` to produce the theorem number.

It would be a convenience to the reader if in each appendix, you repeat the statement of the relevant theorem before giving the proof.

If you feel the number of lettered appendices A, B, C, D, etc are becoming excessive, you could move down the hierarchy. Most thesis templates are based on the `book` document class, in which the top-level text element is the `chapter`. So if you want, you could write

```
\backmatter
\chapter{Additional Proofs}
\section{Proof of the Snargleberg--Veeblefester Theorem (Theorem \ref{snargleberg})}

Blah blah blah.

\section{Proof of the Dumbledore Lemma (Lemma \ref{dumbledore})}

Expecto Patronum.

```

Producing something like:

> 
> A. Additional proofs.
> 
> 
> A.1. Proof of the Snargleberg–Veeblefester Theorem (Theorem 1.2.3)
> 
> 
> Blah blah blah.
> 
> 
> A.2. Proof of the Dumbledore Lemma (Lemma 2.3.4)
> 
> 
> Expecto Patronum.
> 
> 
> 

I disagree with Pete L. Clark's suggestion to just leave the appendices with non-descriptive titles like "Appendix A". Using descriptive appendix titles will help keep the reader from getting lost.
I would think twice about including these results in appendices at all. You have one appendix for each chapter and each "contains some proofs that did not belong in the chapter itself (e.g. proofs of lemmas and technical details)". Why doesn't that belong in the chapter itself? That sounds like exactly the sort of material that I would expect to take up space in a math PhD thesis. You may want to organize things so that the most technical bits can be quickly identified and skipped by the uninterested reader, but putting them in appendices doesn't sound quite right to me. Appendices should contain material which is *ancillary* to the thesis, not the technical core of the thesis.

Anyway, if you decide to go for the multiple appendices: I would call the Appendix "The Appendix" if there is one of them, and if there is more than one "Appendix A", "Appendix B", and so forth. 

**Added**: After more thought, I agree with @Nate Eldredge's disagreement. If there is more than one appendix, you should probably give some help to the reader by saying what is in each one. Now that I seriously contemplate this possibility though [not that seriously; I still am not convinced that this is a good use of appendices at all, but whatever...] I find the question a bit weird: in that the OP can see his thesis, he is in a much better position than we to make the titles. But a simple, descriptive title should be fine.