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

Why isn't this undecidable problem in NP?

18 votes
Accepted

Why is Turing completeness right?

16 votes
Accepted

Universality of the Toffoli gate

16 votes
Accepted

Are there improvements on Dana Angluin's algorithm for learning regular sets

13 votes
Accepted

Organisation and Architecture of Quantum Computers

13 votes

Is a PDA as powerful as a CPU?

12 votes

Are there NP problems, not in P and not NP Complete?

12 votes
Accepted

What's flawed about the "save-the-input" method of reversible computing?

11 votes

Reconstructing Graphs from Degree Distribution

11 votes

Number of words in the regular language $(00)^*$

10 votes
Accepted

Hardness of mixed 3-SAT and 2-SAT formula

9 votes

Time Complexity of Genetic Algorithms

8 votes
Accepted

Quantum computers and computable functions

7 votes
Accepted

Clarifications on polynomial reducibility for problems in P and NP-complete

6 votes

How fast can we decide whether a given DFA is minimal?

6 votes
Accepted

Does reachability belong to P?

5 votes
Accepted

How to deal with questions having two or more asymptotic notations

5 votes

How to prove that $n(\log_3(n))^5 = O(n^{1.2})$?

5 votes
Accepted

Does an enumerator print the first occurrence of a word in finite time?

3 votes

Help me resolve my doubts about infinities, exemplified by an example of non DFA acceptable language

3 votes
Accepted

Canonical reference on agent-based computing

3 votes

Fundamental algorithms in formal language-automata theory

3 votes
Accepted

Genetic algorithm: What is the expected number of strings that are explored?

2 votes

How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma?

2 votes
Accepted

A NPDA for the language $L = \{w \mid w \in \{a,b,c\}^*, n_c(w) = n_a(w) + n_b(w)\}$

1 vote

Prove that the language L = {a^(m+n) b^m a^n | m, n ≥ 0} ∪ {a^m b^n a^(m+n) | m, n ≥ 0} is not regular

1 vote

What's the purpose of the "o(1-o)" in the back propagation algorithm