I am unable to quantify it as there are many problems which are in polynomial time and certain problems can be reduced to polynomial time.How exactly to quantify them?


Are you talking about solvable versus unsolvable, or polynomial time versus not polynomial time?

Assuming we're restricted to problems that can be described by a finite expression in a given language having a finite alphabet, the number of problems is countably infinite.

There are countably many solvable problems (since if $A$ is one solvable problem, and $B$ is any problem, you can get a solvable problem of the form "do $A$ or $B$"), and countably many unsolvable problems (since if $C$ is one unsolvable problem, and $B$ is any problem, you can get an unsolvable problem of the form "do $B$ and $C$").

  • $\begingroup$ Thanks got it I was talking about solvable versus unsolvable $\endgroup$ – ten do May 15 at 1:11
  • 1
    $\begingroup$ There's apparent tension here with the idea that for any real number $x$, there should be problems like "Is $x$ computable?" or "Is the function $f$ defined by $f(z)=xz$ differentiable?", so there should be uncountably many "problems". I suppose the resolution lies in saying that almost all real numbers cannot be named—which is pretty weird really; this supposedly familiar object which we introduce to grade schoolers consists mostly of things forever beyond our ken. $\endgroup$ – Kundor May 15 at 2:51
  • $\begingroup$ @Kundor thanks got it $\endgroup$ – ten do May 15 at 23:53

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.