Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
I think most important is to first have to ask yourself why you want to define a new complexity class. The answer to that should also essentially be the answer to your original question. Complexity classes can be and are defined in many different ways - compare, e.g., the definitions of DET, NP, BPP, PPAD, TFNP, MAX-SNP, NC^1 (uniform and nonuniform). But despite their varied definitions they all had a good underlying motivation. If you have a good motivation for defining a certain class of problems, it probably shouldn't matter if it fits the standard mold of complexity class definitions. –  Joshua Grochow May 14 at 15:36
add comment

2 Answers 2

up vote 12 down vote accepted

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.

share|improve this answer
add comment

First of all, you must justify why the class is important enough to have a name. With $ 2^{ 2^{ \mathbb{N}_0 } }$ classes lying around we can afford to be very picky. So, assuming your research has led you to define an interesting property the problems in class have (this can be semantic or syntactic), let's call it "property X" you should first investigate the class on your own. I would try to answer the following questions:

  • First step: Investigate the literature in the related research area. Has a class on objects from your research been defined? Ask experts in the area: "are there any known classes about this?". A little time spent asking might allow you to avoid losing time on something that is already known. So, let's assume you asked around and you have decided your class is unique enough and relevant to deserve study.

  • Does "property X" specify a computation model? Is the model randomized or non-deterministic? Is the model uniform?

  • How does your class behave under "usual" operations (union, complement, transitive closure etc.) . Note that if you work on a specific computation model, some questions may be trivial or easy to answer.

  • How does your class compare to other known classes? If it's a specific model, how does it compare to "canonical" classes of that model (e.g. $\mathbb{NP}$ for non-deterministic TM, $\mathbb{BPP}$ for randomized TM, and so on)? Did you find some interesting closure property (e.g. is your class closed under complement? then perhaps non-determinism isn't a good framework to go on).

  • How do well-known problems compare with your class? Does it contain complete problems, i.e. can you make it so that a well-known problem has "property X"? If you cannot, for what known notions of reductions is your class closed under? If those you know don't fit the class, can you use the closure properties you found above to define one that does and is less powerful than the class itself?

  • Can you find problems that are hard for your class under some reduction that makes sense from the above step? Are they complete too? How do these problems compare with the well-known problems you investigated in the previous point? The problem < L | L has property X > should be hard for the class. Is it also complete?

Now, for most classes you should probably not be able to answer all those questions, but you can answer some, maybe most of them. Now you have an idea how this class behaves and whether it would be interesting for your line of research. If you deem it worthy, you can start asking people from the area, e.g. your advisor or a faculty that is familiar with the subject, what they think.

share|improve this answer
1  
I would add to the list of "usual" operations: closure under various types of reductions (such as $AC^0$-reductions, poly-time many-one reductions, poly-space many-one reductions, poly-time Turing reductions, etc.) –  Joshua Grochow May 14 at 15:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.