1
$\begingroup$

Am I correct in saying that there are two ways to categorise a problem in complexity theory:

  • Find an algorithm that solves it. If the algorithm runs in polynomial time, then we can put it into P-class. If not, then we can put it into EXP.

  • Provide a reduction that this problem is no hard than another problem, to which we know the complexity class for.

If I cannot find a reduction and I do not have an algorithm, what is the "default" complexity class? I'm guessing it would be in the class of problems which cannot be solved until we find an algorithm.

$\endgroup$

bumped to the homepage by Community 23 hours ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

  • 1
    $\begingroup$ There are algorithms whose running time is more than exponential. $\endgroup$ – Yuval Filmus Jun 20 at 13:15
  • $\begingroup$ @YuvalFilmus understood. Is the rationale correct though? "We categorise problems based on the best known algorithm or their relation to other problems who we know the complexity classes for" ? $\endgroup$ – WeCanBeFriends Jun 20 at 20:04
  • 1
    $\begingroup$ Yes, this is a nice summary. $\endgroup$ – Yuval Filmus Jun 20 at 20:04
  • $\begingroup$ @YuvalFilmus got it thank you $\endgroup$ – WeCanBeFriends Jun 20 at 20:06
0
$\begingroup$

Your reasoning seems correct, but you are missing a crucial step once the second bullet point is done with: You check that your problem is also complete for the class $C$ you have found for it. For instance, if you have a problem $P$ and show it is reducible to a complete problem in $\mathsf{PP}$, then you are not done yet. For all we know, $P$ could be $\mathsf{PP}$-complete, but it could also be in $\mathsf{NP}$, or $\mathsf{BPP}$, etc. Therefore, to finish classifying $P$, you should be able to find a class it is complete for—if possible; after all, there are classes which are not closed under (poly-time many-one) reductions—, or provide some good evidence why it could not be in a class which is known (or conjectured) to be strictly below $C$.

If I cannot find a reduction and I do not have an algorithm, what is the "default" complexity class?

Assuming your problem is decidable, the "default" complexity class is $\mathsf{R}$, the class of recursive languages. Improving on this is only possible by producing an algorithm whose time complexity you can prove or, alternatively, proving a reduction to some other problem for which this is the case; that is, essentially what you wrote in your question. There is no such thing as a "class of problems which cannot be solved until we find an algorithm" in complexity theory; that would be the domain of computability theory (i.e., problems which are not known to be decidable).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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