0
$\begingroup$

I'm looking for an example of a randomized algorithm that halts with probability 1 (halts almost surely), uses only logarithmic space (worst case) and whose expected run time is not polynomial in the size of the input.

$\endgroup$
5
  • $\begingroup$ Can you edit your question to define "always halts" more precisely, please? If the probability of not halting is 0, does that qualify as "always halts"? Do you mean for all inputs, the probability that it halts is 1? Or do you mean that for all inputs and all possible coins (choices of random values), it halts? $\endgroup$
    – D.W.
    Dec 29, 2021 at 6:40
  • $\begingroup$ Please don't use "EDIT:". Rather than appending more information at the end, please revise your question so that it reads well for someone who encounters it for the first time. We're hoping to build up an archive of high-quality questions that will be useful to others in the future. See cs.meta.stackexchange.com/q/657/755 for more details. $\endgroup$
    – D.W.
    Dec 29, 2021 at 22:22
  • $\begingroup$ Can you now clarify what you mean by "run time"? Do you mean "expected running time" (expectation taken over the random choices made by the algorithm, for the worst-case input)? Do you mean worst-case running time (both the worst-case input, and the worst-case set of random choices)? Something else? It affects the answer. $\endgroup$
    – D.W.
    Dec 29, 2021 at 22:24
  • $\begingroup$ In essence, halts almost surely, worst case logarithmic space, worst case exponential time $\endgroup$ Jan 2, 2022 at 18:31
  • $\begingroup$ This still doesn't answer what you mean by "worst case". Does that mean worst over all possible random choices that happen during execution of the algorithm, as well as all possible inputs? If you'd like an answer, I recommend that you edit your question to specify this very explicitly and clearly in the question. Don't force us to guess -- as then if we answer based on some guess at what you're asking, and it wasn't the assumption you were hoping for, then both you and we have wasted our time. $\endgroup$
    – D.W.
    Jan 3, 2022 at 2:29

1 Answer 1

2
$\begingroup$

If I understand you correctly, I don't think such an algorithm exists. Any algorithm that uses only log space and halts could not run in exponential time, because there is at most polynomial number of unique configurations of the machine. This applies to randomized algorithms (i.e. probabilistic Turing machines) as well, because every branch of the probabilistic TM has to halt in polynomial time before running out of possible configurations for that branch.

$\endgroup$
2
  • $\begingroup$ While i believe this is correct accordingly to my previous formulation, i have edited it and am quite sure there should exist an algorithm in the new formulation. $\endgroup$ Dec 30, 2021 at 1:45
  • $\begingroup$ @JoséDuartedeAzevedoeCunha, what makes you sure that one should exist? Did you encounter this question somewhere? Can you tell us about the context behind this question and why you believe such an algorithm should exist? $\endgroup$
    – D.W.
    Jan 3, 2022 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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