Timeline for A "natural" decidable problem not in $\mathsf{NP}$?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Mar 19, 2013 at 16:36 | vote | accept | templatetypedef | ||
| Mar 19, 2013 at 14:09 | history | edited | Niel de Beaudrap | CC BY-SA 3.0 |
revised to include squaring operation
|
| Mar 18, 2013 at 18:03 | comment | added | Thomas Klimpel | Yes, squaring can be achieved in-line. But this increases the size of the input, and complexity classes depend on how you measure the size of the input. It wouldn't matter if it were just a constant factor, but you can apply squaring multiple times. In effect, it's easy to see that squaring can be used to emulate exponentiation such that the size of the input only increases by a constant factor. | |
| Mar 18, 2013 at 14:11 | comment | added | Niel de Beaudrap | @ThomasKlimpel: This doesn't really make sense to me. Can't squaring be achieved in-line anyway, by replacing e.g. $(a|bc)^2 = (a|bc)(a|bc)$? | |
| Mar 16, 2013 at 11:04 | comment | added | Thomas Klimpel | Wikipedia's List of PSPACE-complete problems contains "Equivalence problem for regular expressions". The EXPSPACE-complete problem needs the additional operator of squaring, according to Wikipedia's EXPSPACE-page. | |
| Mar 16, 2013 at 5:12 | comment | added | vzn | nearly identical, determining if $L=\Sigma*$ for regular expressions with exponentiation | |
| Mar 15, 2013 at 18:14 | history | answered | Niel de Beaudrap | CC BY-SA 3.0 |