Skip to main content
Share Your Experience: Take the 2024 Developer Survey
sdcvvc's user avatar
sdcvvc's user avatar
sdcvvc's user avatar
sdcvvc
  • Member for 12 years, 2 months
  • Last seen more than a month ago
3 votes
Accepted

How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

6 votes

P vs. NP and Godel's Theorems

4 votes

Why doesn't the recursion theorem prove there is an undecidable finite set?

6 votes
Accepted

Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

4 votes
Accepted

Is Half - Palindrome subset of a context-free language context-free?

1 vote
Accepted

PCAs and Kleene's Recursion Theorem

1 vote

Meta-computational complexity?

6 votes
Accepted

Is a kind of reverse Kleene star of a context-free language context-free?

3 votes
Accepted

Why isn't chess an impartial game?

4 votes
Accepted

Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?

4 votes

How can P=NP relate to creativity and proof automation, as said by Scott Aaronson?

6 votes
Accepted

Prove Language Is Union of Fninitely Many Arithmetic Progressions

6 votes

Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?

3 votes
Accepted

Efficient computation of Kronecker product

3 votes
Accepted

Acyclic Graph in NL

2 votes

If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

5 votes
Accepted

Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$

13 votes
Accepted

Is it possible for a language and its complement to both be unrecognizable?

10 votes
Accepted

If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

5 votes
Accepted

Is DSPACE properly contained in NSPACE?

15 votes

Examples of context-free languages with a non-context-free complements

4 votes
Accepted

Why is the difference of two NP-complete languages not in NP?

7 votes
Accepted

Are regular and context free languages closed against making them prefix-free?

2 votes

Example for a non-trivial PCP verifier for an NP-complete problem

5 votes
Accepted

BPP upper bound

7 votes

Infinite languages and undecidable languages

2 votes
Accepted

Can a language have $\Sigma^{*}$ as its syntactic monoid?

7 votes

Can P=PSPACE and PSPACE problems be formulated as $\Pi_1$ formula?

2 votes

Is $A$ regular if $A^{2}$ is regular?

10 votes
Accepted

Which non-regular languages are in $AC^0$?