Skip to main content
Theoretical Computer Science

Good Answer

 Good Answer
Answer score of 25 or more. This badge can be awarded multiple times.
Awarded 663 times.
If an abstract machine can simulate itself, does that make it Turing complete?
Awarded Aug 10 at 7:39
What Books Should Everyone Read?
Awarded Jul 30 at 13:49
What Books Should Everyone Read?
Awarded Jul 30 at 13:49
Major unsolved problems in theoretical computer science?
Awarded Jun 28 at 16:48
Is there a logic without induction that captures much of P?
Awarded Apr 21 at 7:05
Why have we not been able to develop a unified complexity theory of distributed computing?
Awarded Apr 7 at 8:35
Can we quantify the "degree of quantumness" in a quantum algorithm ?
Awarded Mar 30 at 9:11
Is there a typed lambda calculus which is consistent and Turing complete?
Awarded Mar 11 at 9:47
What papers should everyone read?
Awarded Mar 5 at 11:15
What are the differences between logical relations and simulations?
Awarded Feb 25 at 6:48
What Lecture Notes Should Everyone Read?
Awarded Jan 14 at 1:06
Why isn't TheoretiCS very popular yet?
Awarded Jan 4 at 0:55
Partition a graph into node-disjoint cycles
Awarded Dec 30, 2023 at 4:35
Kolmogorov's conjecture that $P$ has linear-size circuits
Awarded Dec 16, 2023 at 22:10
A probabilistic set with no false positives?
Awarded Dec 3, 2023 at 0:06
"Almost all objects have property P" vs. "It is easy to test whether an object has property P"
Awarded Nov 10, 2023 at 10:17
Relation between $AC^0$ and regular languages
Awarded Nov 1, 2023 at 18:01
Can it be determined if language L lies in NP?
Awarded Oct 24, 2023 at 4:27
How can relational parametricity be motivated?
Awarded Oct 6, 2023 at 7:40
How "hard" is it to maximize a polynomial function subject to linear constraints?
Awarded Sep 28, 2023 at 18:22
Recent advances in computer science since 2010?
Awarded Sep 25, 2023 at 11:25
What is the big version of NC?
Awarded Sep 25, 2023 at 8:51
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
Awarded Sep 21, 2023 at 15:49
What would be the consequences of $\mathsf{PH=PSPACE}$?
Awarded Aug 8, 2023 at 10:47
Why does Coq have Prop?
Awarded Jul 7, 2023 at 15:37
Book on Probability
Awarded Jun 4, 2023 at 12:57
Deciding emptiness of intersection of regular languages in subquadratic time
Awarded May 31, 2023 at 9:22
Universal Function approximation
Awarded Apr 26, 2023 at 23:41
How to make the Lambda Calculus strong normalizing without a type system?
Awarded Apr 17, 2023 at 3:25
Theoretical Computer Science vs other Sciences?
Awarded Mar 19, 2023 at 22:41
What constitutes denotational semantics?
Awarded Mar 16, 2023 at 13:03
Can any program be implemented mechanically?
Awarded Jan 21, 2023 at 20:11
What's the status of Babai's Graph isomorphism result?
Awarded Jan 4, 2023 at 1:33
is "spaghetti sort" really O(n) (even as a thought experiment) ?
Awarded Dec 25, 2022 at 18:10
How to publish a paper?
Awarded Dec 25, 2022 at 8:12
NP-hard problems on trees
Awarded Nov 9, 2022 at 7:20
NP-hard problems on trees
Awarded Nov 8, 2022 at 10:25
Interactive proofs for levels of the polynomial hierarchy
Awarded Oct 21, 2022 at 22:33
How does the BosonSampling paper avoid easy classes of complex matrices?
Awarded Oct 14, 2022 at 0:15
Shallow versus Deep Embeddings
Awarded Sep 28, 2022 at 16:35
Can a computer simulate itself as part of a simulated world?
Awarded Aug 30, 2022 at 8:21
Techniques for showing that problem is in hardness "limbo"
Awarded Aug 18, 2022 at 20:33
Concise introduction to algorithms for mathematicians
Awarded Aug 2, 2022 at 7:42
Oracle Construction for Grover's Algorithm
Awarded May 18, 2022 at 17:57
Are there languages that are not in RE nor CO-RE?
Awarded Apr 5, 2022 at 15:41
Major unsolved problems in theoretical computer science?
Awarded Mar 15, 2022 at 1:56
Empirical results in CS papers
Awarded Jan 31, 2022 at 13:06
Is finding Logspace reductions harder than P reductions?
Awarded Jan 24, 2022 at 23:50
Are research papers hard to read?
Awarded Nov 9, 2021 at 13:11
Is Descriptive Complexity dead?
Awarded Nov 5, 2021 at 16:46
What's the relation and difference between Calculus of Inductive Constructions and Intuitionistic Type Theory?
Awarded Oct 9, 2021 at 8:55
Symbolic Execution is a case of Abstract Interpretation?
Awarded Oct 7, 2021 at 12:21
Do any quantum algorithms improve on classical SAT?
Awarded Sep 24, 2021 at 11:57
EXPSPACE-complete problems
Awarded Sep 23, 2021 at 10:07
Does $VP \neq VNP$ imply $P \neq NP$?
Awarded Aug 25, 2021 at 12:50
Theoretical explanations for practical success of SAT solvers?
Awarded May 22, 2021 at 16:57
Is it NP-hard to play international draughts correctly?
Awarded May 10, 2021 at 17:53
What are natural examples of non-relativizable proofs?
Awarded Mar 21, 2021 at 15:27
Why would one ever use an Octree over a KD-tree?
Awarded Feb 15, 2021 at 19:32
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
Awarded Feb 8, 2021 at 6:42
1
2 3 4 5
…
12