Timeline for Show Recognizing two Regular Expressions as equal is in PSPACE
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 1, 2023 at 11:50 | answer | added | user1868607 | timeline score: 1 | |
| Jul 11, 2016 at 19:38 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jun 11, 2016 at 19:13 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 12, 2016 at 18:53 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 14, 2016 at 10:47 | history | tweeted | twitter.com/StackCompSci/status/720564027395600384 | ||
| Apr 12, 2016 at 18:35 | history | edited | D.W.♦ | CC BY-SA 3.0 | deleted 16 characters in body |
| Apr 12, 2016 at 6:57 | comment | added | Louis | Maybe look at this question for inspiration. cs.stackexchange.com/questions/24390/… | |
| Apr 11, 2016 at 21:01 | history | edited | Raphael | edited tags | |
| Apr 11, 2016 at 17:14 | history | edited | Yuval Filmus | CC BY-SA 3.0 | added 18 characters in body |
| Apr 11, 2016 at 17:14 | answer | added | Yuval Filmus | timeline score: 5 | |
| Apr 11, 2016 at 17:05 | history | edited | Brandon G | CC BY-SA 3.0 | improved formatting |
| Apr 11, 2016 at 16:49 | comment | added | D.W.♦ | Have you been able to find any algorithm for testing whether regexps $R,S$ are equivalent? If so, what's the best algorithm you've come up with so far? How does it work? What is the space complexity of that algorithm? Do you know the definition of PSPACE? Do you know how to prove that an algorithm is in PSPACE? It sounds like you might need to review the definition of PSPACE. | |
| Apr 11, 2016 at 16:49 | comment | added | D.W.♦ | Welcome to CS.SE! Please edit the question to show us what you've tried and where you got stuck. Do you have any specific question about this problem? We want to help you understand concepts, not do your exercise for you, but you haven't given us much to work with, so it's not clear how to help you. Just copying the text of your exercise into the question doesn't work so well here, because it's hard to tell from that what you are stuck on or why you are having difficulty with the problem. Rather than leaving information in the comments, please edit the question. | |
| Apr 11, 2016 at 16:33 | comment | added | Brandon G | I've been trying to think of different ways to tackle it, but no luck so far. I've thought if you can prove it is in NP, then it is also in PSPACE, but I can't think of any possible poly-time verifier for it. I also can't come up with a PSPACE-complete problem to reduce it to, which is the route that seems more likely. | |
| Apr 11, 2016 at 16:29 | comment | added | Louis | Did you try anything yet? Where did you get stuck? | |
| Apr 11, 2016 at 16:27 | review | First posts | |||
| Apr 12, 2016 at 3:59 | |||||
| Apr 11, 2016 at 16:21 | history | asked | Brandon G | CC BY-SA 3.0 |