patternMinor
One $O(n^k)$ algorithm requiring only one $O(2^n)$ computation (for all n instances) is P or NP
Viewed 0 times
computationallinstancesalgorithmoneforonlyrequiring
Problem
Let $a$ one decision problem and $A$ one algorithm solving it in $O(n^k)$.
But, to construct $A_n$ we need to compute certain thing (strategy path, magic numbers, ...), we can compute that using certain general algorithm $R$ in $O(2^n)$.
Obiously, $A$ is polynomial (then, all $A_n$ are in P) and $R$ is exponential.
We can not solve big instances because $R$ is not practical.
But, in practice, we will can solve big instances after a big effort computing $A_n = R(n)$.
My question is twofold:
-
How are such problems considered in theory?
Have they been studied explicitly? Is there a particular case? some literature to read?
-
How are such problems solved in practice?
Have they been studied in general? Is there is a particular case? some literature to read?
But, to construct $A_n$ we need to compute certain thing (strategy path, magic numbers, ...), we can compute that using certain general algorithm $R$ in $O(2^n)$.
Obiously, $A$ is polynomial (then, all $A_n$ are in P) and $R$ is exponential.
We can not solve big instances because $R$ is not practical.
But, in practice, we will can solve big instances after a big effort computing $A_n = R(n)$.
My question is twofold:
-
How are such problems considered in theory?
Have they been studied explicitly? Is there a particular case? some literature to read?
-
How are such problems solved in practice?
Have they been studied in general? Is there is a particular case? some literature to read?
Solution
If the "thing" is polynomial-size, then it's in P/poly, a class that has been studied intensively, although this is a very interesting subclass of it which I don't believe been studied. If you have an algorithm that falls into this subclass, I believe theoretical computer scientists might be interested in it.
If the "thing" can be exponential size, then the "thing" could just be a table of all the answers for the instances of size $n$, so all algorithms in EXPTIME would fall into this class. And in fact, this class would be equal to EXPTIME, since the algorithm R followed by A is in EXPTIME.
If the "thing" can be exponential size, then the "thing" could just be a table of all the answers for the instances of size $n$, so all algorithms in EXPTIME would fall into this class. And in fact, this class would be equal to EXPTIME, since the algorithm R followed by A is in EXPTIME.
Context
StackExchange Computer Science Q#14810, answer score: 7
Revisions (0)
No revisions yet.