Hints¶
Q1¶
PSPACE or not?
Are the following problems in PSPACE? Why or why not?
- SAT
- SSP
- PATH
- HAMPATH \(=\{\braket{G,s,t} \mid G \text{ is a directed graph with a Hamiltonian path from } s \text{ to } t\}\)
-
HAMCYCLE \(=\{\braket{G} \mid G \text{ is a directed graph with a Hamiltonian cycle}\}\)
What is a Hamiltonian cycle?
Recall that "Hamiltonian cycle" means a "path that starts at a vertex, visits every vertex of \(G\) once, then returns back to the start vertex."
Example:
All are in PSPACE because they are all in NP, and NP is a ........... of PSPACE.
Q2¶
Binary strings with equal 0s and 1s
Show that the language of all binary strings with equal \(0\)'s and \(1\)'s is in L.
Read the input from left to right. Maintain a counter on the work tape with initial value zero, and increment or decrement it when reading "\(0\)" or "\(1\)" respectively.
Reject if the counter ever becomes .........., and accept if the counter is .......... at the end of the input.
Since the counter can never exceed the input length \(n\), it is an \(O(.......)\)-bit number, so this only requires a work tape with \(O(\log n)\) bits.
Tip
In general, any language which can be recognized by a machine with any constant number of counters is in L.
Q3¶
Balanced brackets
Show that testing for balanced brackets is in L.
The corresponding language looks like:
This is the same as the previous one, just replacing \(0\)'s and \(1\)'s by \((\)'s and \()\)'s.
Read the input from left to right. Maintain a counter on the work tape with initial value zero, and increment or decrement it when reading "\((\)" or "\()\)" respectively.
Reject if the counter ever becomes ..........., and accept if the counter is ......... at the end of the input.
Since the counter can never exceed the input length \(n\), it is an \(O(........)\)-bit number, so this only requires a work tape with \(O(\log n)\) bits.
Q4¶
Palindromes over {0, 1}
Show that the language of palindromes over the alphabet \(\{0, 1\}\) is in L.
Simulate a for-loop that keeps track of the indices of the symbols that need to be compared.
Recall that \(w\) is palindrome if \(w=w^R\).
To check that \(w=w^R\), we check that each symbol matches the one in the position opposite to it from the end of the string, i.e. \(w_i = w_{.......}\) for \(i=0,1,\ldots,n-1\) where \(n=|w|\).
A log-space TM can keep track of its current position by ............ or ............ a counter as it moves left or right. It can also carry out for/while-loops (in log-space) as long as the counters have values polynomial in \(n\), since then the counters are \(O(\log n)\)-bit numbers, and can all fit in \(O(.......)\) space (as long as the number of counters is constant).
............