New answers tagged complexity
2
Is there an efficient algorithm for calculation of continued fraction expansion from decimal digits?
I have not solved this exact problem, but a nearby problem is finding rational approximations to decimals (eg 0.333 => 1/3), for which I have used an algorithm called "mediant search". Under the hood, this search traverses an (implicit/infinite) data structure called the "Stern-Brocot tree", which is a novel way to enumerate every possible rational number in ...
1
When considering a problem in a Computational Complexity context, an instance for the problem is just an input to the problem encoded in a manner that works with the underlying model of computation. For a Turing Machine, you would want your input to be encoded in the input alphabet $\Sigma$, which could be as simple as $\Sigma = \lbrace 0, 1\rbrace$ if your ...
3
Pragmatically, an instance just means an input/output pair of an algorithm.
I think a better example of a reduction would be transforming multiplication into repeated addition. For example, the single multiplication "instance", $4*7$, can be transformed into $7+(7+(7+7))$, three "instances" of the addition algorithm. Reduction is all about finding ways to ...
Top 50 recent answers are included
