Timeline for Prove that a set A is semi-decidable if and only if there is a polynomial time relation R(x,y)
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2020 at 2:04 | comment | added | Caleb Stanford | @DeeDee Sorry I don't have time to write a detailed answer right now :( Try asking a new question! | |
| Jun 22, 2020 at 1:26 | comment | added | DeeDee | Does this mean that all semi-decidable problems are in NP? i don't? get it or do we need some extra conditions such as y has to be polynomially long? thanks! | |
| Feb 27, 2020 at 22:05 | comment | added | Caleb Stanford | Also checking the last config is accepting means you check that the head is in an accepting state; that should be at most $O(|y|)$ instead of $O(|x|)$. Probably much less than $|y|$ but $|y|$ is an upper bound. | |
| Feb 27, 2020 at 22:03 | comment | added | Caleb Stanford | @John Mostly right -- except for Turing machines checking two strings for equality is quadratic instead of linear, so $O(|x|)^2$ to check $x$ is on the tape. What matters is that this is polynomial in $|x|$. | |
| Feb 27, 2020 at 22:02 | history | edited | Caleb Stanford | CC BY-SA 4.0 |
deleted 20 characters in body
|
| Feb 27, 2020 at 19:42 | comment | added | John | So it takes O(|x|) to check x is on the tape. O(|y|) to check y is a valid transition sequence. O(|x|) to check the last configuration in y is accepting, right? | |
| Feb 27, 2020 at 19:22 | history | answered | Caleb Stanford | CC BY-SA 4.0 |