If I wanted to define my own complexity class would you first define it as a set of problems with reductions to those problems? How would one go about doing this?
if I were to define a new complexity class how should I start?
cc.complexity theory;reference request
First you would search around and check e.g. the complexity zoo, because many, many classes are already defined and you don't want to redefine one that is already known by some other name.The ways I know of are:Define a complete problem and a notion of reduction; the class consists of all problems so reducible to that problem. This is usually only possible for so-called syntactic complexity classes -- see the question Semantic vs Syntactic Complexity Classes -- which tend to also have a nice definition in terms of a model of computation. (E.g. $\mathsf{NP}$ can be defined as all languages that are polytime mapping-reducible to $\mathsf{3SAT}$; or as all languages decidable by a polytime nondeterministic TM.)Define a model of computation and what it means for that model to decide/compute a language/problem; the class consists of all languages/problems for which there exists such a model of computation that decides/computes the language/problem. This works for probabilistic classes like $\mathsf{BPP}$, but also for more exotic models like quantum classes, circuits, interactive protocols, or finite automata for that matter. This is probably the method you'd go for, and for more detail, maybe look at examples of all the above types (e.g. $\mathsf{BPP, BQP, ACC, IP, MA, PCP, REGULAR}$).Perhaps those more expert than I am can say if there are other major methods that are missing, or expand on these if needed.