6
votes
Accepted
What else measures are used to compare algorithm efficiency apart from Time and Space complexities?
When it comes to the numerical methods used in science and engineering, one important measure is numerical accuracy.
- 991
5
votes
Accepted
Read-once complexity of a matrix problem
The computation of the erasing machine can be expressed as a read-once branching program.
A branching program is a DAG with a unique source and two sinks, labelled "Yes" and "No". ...
- 277k
4
votes
Accepted
Unions of PSPACE-comlete problems that are PSPACE-complete?
Let $A,B\subsetneq\Sigma^*$ be $\text{PSPACE}$-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^*$ and $A\cup B\in\text{PSPACE}$. Does it follow that $A\cup B$ is $\text{PSPACE}$-...
- 39k
4
votes
PSPACE≠co-NP?Is the statement true?
If P = PSPACE then since $\text{P} \subseteq \text{coNP} \subseteq \text{PSPACE}$, we can conclude that coNP=PSPACE, and by contrapositive this means that if $\text{coNP} \neq \text{PSPACE}$ then $\...
- 529
3
votes
Question about ALL-NFA in PSPACE
Note that the procedure decides the complement of $ALL_{NFA}$, which is sufficient as $PSPACE = NPSPACE$.
The procedure checks whether the NFA $M$ rejects some input. The idea is simple, we actually ...
- 2,911
2
votes
ALL_{NFA} is PSPACE-complete
Let's show a generic PTIME reduction from any language in $\text{PSPACE}$ to $ALL_{NFA}$.
Let $L \subseteq \Sigma^*$ be a language in PSPACE, and let $T$ be a TM that decides $L$ with polynomial space-...
- 2,911
2
votes
Accepted
How to allocate memory for prime numbers
I suggest you allocate space for
$$U = \max(N/(\ln(N) - 1.1), N/\ln(N) + 2000).$$
This will be quite close to the true number. For instance, for $N=10^7$, it is only 1284 larger than the true number. ...
D.W.♦
- 159k
2
votes
Accepted
Is there a language $L$ such that $L \in DSPACE(1) \setminus DTIME(1)$?
No. Consider the language
$$L = \{x \in \{0,1\}^* \mid x \text{ has even parity}\},$$
i.e.,
$$L = \{x_1 \cdots x_n \mid x_1 + x_2 + \cdots + x_n \equiv 0 \pmod 2\}.$$
This language is in $\textsf{...
D.W.♦
- 159k
2
votes
Accepted
How to construct complement of NFA universality?
Consider the language $ALL_{NFA} = \{\langle A\rangle: \text{$A$ is an NFA with $L(A) = \Sigma^*$}\}$.
If you want a non-PTIME reduction from $\overline{ALL_{NFA}}$ to $ALL_{NFA}$, then you can simply ...
- 2,911
2
votes
Is it possible to sort numbers in linear time and constant extra space?
If you require a comparison-based sorting algorithm akin to quicksort and merge sort, the answer is "No." Simply put, it can be proven that sorting an array of $n$ elements using a ...
1
vote
I am struggling to define the space complexity of a turing machine
Yes, if you can define such a TM that can solve the problem in space $O(\log n)$ that is sufficient to show that the problem is in class $A$. You should then prove that this TM never uses more than $O(...
- 174
1
vote
PSPACE and Polynomial reduction
Correct: you can choose $C$ to be any $\text{PSPACE-complete}$ language.
The only known counter-examples to this claim are ones where $C$ or $A$ are trivial, and hence, sadly, a counter-example would ...
- 2,911
1
vote
PSPACE and Polynomial reduction
Regarding 1: choose $C = \{0x \mid x \in A \} \cup \{1x \mid x\in B\}$.
Regarding $2$: $B \le_P \emptyset \implies B=\emptyset$ however $\{\varepsilon\} \le_P B \implies B \neq \emptyset$.
Regarding $...
- 29.5k
1
vote
Transform OTM for Problem π to DTM ∈ DSPACE(n)
It depends on the oracle. If $\pi$ is solved by the OTM using an oracle for a non-computable problem (non-decidable language), then there might not be a DTM that can solve $\pi$ without an oracle. ...
D.W.♦
- 159k
1
vote
Accepted
$NL$ Leaf languages and $PSPACE$
You are omitting some very important details. In the exercise, the Turing machine $N$ is required to halt on all its possible computation paths using exactly $p(n)$ steps, where $n$ is the size of the ...
- 29.5k
1
vote
Why is $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$?
My experience is that $\log^2 n$ normally means $(\log n)^2$, unless context indicates otherwise.
The result follows from the fact that $DSPACE(f(n)) \subseteq DTIME(2^{f(n)})$ (proven by using the ...
D.W.♦
- 159k
1
vote
Accepted
Quick and space-efficient way to find whether two sets intersect
Use a partitioned Bloom filter for testing set intersection. It has lower FPR than unpartitioned (standard) Bloom filters.
To intersect two partitioned Bloom filters:
AND the bit vectors for all the ...
- 261
1
vote
Show Recognizing two Regular Expressions as equal is in PSPACE
A good account of this result is in the lecture notes of Dexter Kozen, although the original work of Meyer and Stockmeyer contains a refined space bounds. You may consult that version in Stockmeyer's ...
- 2,194
Only top scored, non community-wiki answers of a minimum length are eligible