10
$\begingroup$

I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic.

This is my reasoning, and I would like to know if (1) this is already known or (2) I misunderstood something or (3) I just found out something useful:

$P_{CTC}$ is the class of problems that can be solved by putting polynomial amounts of data in a time machine.

$BPP_{path}$ is the class of problems that can be solved by postselecting in a probabilistic Turing machine, i.e. ignoring cases you do not care about.

$P_{CTC}\subseteq BPP_{path}$ because you can simulate a closed time-like curve with postselection like this: Scan the entire program in the beginning, both state and memory. Then, after processing, do so again and postselect so that you only return if the state & memory now are exactly equal to the start state & memory (except for a single bit that says whether or not this is the first iteration, to prevent an infinite loop).

$BPP_{path}\subseteq P_{CTC}$ because you can simulate postselection like this: If the message from the future starts with $1$, send the message $0$ into the past. Otherwise proceed as normal. When you get to the step where you would normally post-select, send a 1 into the past iff. you want to ignore this timeline, else a $0$. The only consistent version is now the one where you both receive and send a 0 because you were satisfied with the results.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I have absolutely no idea about this topic, but, in this paper link they say that the class P_CTC is equal to PSPACE and BPP_PATH is equal to POST_BPP that is contained in P with an NP oracle. So the two classes are probably not the same $\endgroup$
    – rotia
    Commented Nov 17, 2016 at 19:12
  • $\begingroup$ That's good to know! I wouldn't say this shows that the two classes are not the same, though: It just means that if they are the same, then PSPACE=P^NP. It makes it less likely to be true because someone else could have discovered this connection earlier if it was true, but it also means that IF approach IS correct, then it will have useful consequences. $\endgroup$
    – Florian Dietz
    Commented Nov 20, 2016 at 12:42
  • $\begingroup$ The sketch of your proof that "P_CTC is in BPP_PATH" is the culprit in my view. One issue is that it is not obvious how your postBPP machine properly retains consistent states of the polynomial number of CTC registers. P_CTC is not simply polynomial time with time travel. There are very specific causal consistency criteria that need to be enforced. These constraints are what give the machine the ability to find partial fixed points easily, which is arguably more general than mere post selection. I encourage you to carefully revisit the formal definition of P_CTC. $\endgroup$
    – mdxn
    Commented Feb 20, 2017 at 0:35

1 Answer 1

Reset to default
0
$\begingroup$

I believe I have found the answer: The proof is wrong. BPP_PATH is not in P_CTC because P_CTC is required to give a single definite answer, while BPP_PATH is a probabilistic algorithm, so the second reduction does not work. For it to work, one would have to use the time-travel information to count the number of successes of the probabilistic algorithm vs the number of its failures. I have no idea how to do this, or if it even can be done (probably not).

Improve this answer
$\endgroup$
2
  • $\begingroup$ ...and five minutes later I am no longer sure. P_CTC = PSPACE, and can't PSPACE simulate BPP? $\endgroup$
    – Florian Dietz
    Commented Nov 21, 2016 at 15:19
  • 2
    $\begingroup$ You are confusing yourself. Deterministic machines are basically probabilistic ones with zero tolerance for error and no access to randomness. If a candidate machine can answer the same questions without the error, then there's no problem. There is no necessity to be wrong just as often. Regardless, PSPACE lets you simulate a BPP machine easily by being able to test every random string and manually calculating the acceptance probability. Since P_CTC = PSPACE, it reasons that there is some equivalent P_CTC machine that can answer the same way given any particular BPP machine. $\endgroup$
    – mdxn
    Commented Feb 20, 2017 at 0:57

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.