Computer Science

Nice Answer

 Nice Answer
Answer score of 10 or more. This badge can be awarded multiple times.

earned this badge 35 times.
Can we read N numbers in O(N) time?
Awarded Aug 7 '20 at 9:07
Turing machine - infinite tape - does that thing exist?
Awarded Oct 30 '19 at 22:00
Is there any nontrivial problem in the theory of serial algorithms with a nontrivial polynomial lower bound of $\Omega(n^2)$?
Awarded Oct 7 '19 at 2:10
What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?
Awarded Aug 10 '19 at 12:35
Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?
Awarded Nov 8 '18 at 16:15
Concrete understanding of difference between PP and BPP definitions
Awarded Jun 5 '18 at 9:37
Can top SAT-solvers factor easy numbers?
Awarded Feb 14 '18 at 10:13
Why is writing down mathematical proofs more fault-proof than writing computer code?
Awarded Dec 20 '17 at 21:29
Clear, intuitive derivation of the fixed-point combinator (Y combinator)?
Awarded Aug 26 '17 at 9:05
Is Karp Reduction identical to Levin Reduction
Awarded Sep 23 '16 at 1:22
Decidable non-context-sensitive languages
Awarded Jun 25 '16 at 7:58
Decision problem such that any algorithm admits an exponentially faster algorithm
Awarded Apr 4 '16 at 6:16
Why, really, is the Halting Problem so important?
Awarded Mar 17 '16 at 6:33
Why are computable functions also called recursive functions?
Awarded Jan 13 '16 at 23:46
What is required for universal analogue computation?
Awarded Jan 6 '16 at 21:38
P-Completeness and Parallel Computation
Awarded Dec 3 '15 at 21:07
What is the time complexity of generating n-th prime number?
Awarded Oct 13 '15 at 0:55
How to prove that a constrained version of 3SAT in which no literal can occur more than once, is solvable in polynomial time?
Awarded Mar 13 '15 at 19:59
If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B
Awarded Jan 31 '15 at 21:14
subsets of infinite recursive sets
Awarded Jan 18 '15 at 21:19
Why is Relativization a barrier?
Awarded Nov 15 '14 at 18:26
Why is quicksort better than other sorting algorithms in practice?
Awarded May 24 '14 at 9:04
What is the definition of P, NP, NP-complete and NP-hard?
Awarded Dec 12 '13 at 23:07
How to prove that a language is not context-free?
Awarded Nov 11 '13 at 19:17
How does one know which notation of time complexity analysis to use?
Awarded Sep 27 '13 at 12:24
Why is this example a regular language?
Awarded May 9 '13 at 1:44
Are there subexponential-time algorithms for NP-complete problems?
Awarded Apr 4 '13 at 13:56
What is the definition of P, NP, NP-complete and NP-hard?
Awarded Feb 13 '13 at 11:51
Why are there more non-computable functions than computable ones?
Awarded Feb 11 '13 at 6:07
Is there a “natural” undecidable language?
Awarded Dec 13 '12 at 10:49
Turing complete and computational power
Awarded Nov 20 '12 at 2:10
How not to solve P=NP?
Awarded May 18 '12 at 17:31
Are there NP problems, not in P and not NP Complete?
Awarded May 14 '12 at 15:44
Sub language is not Turing-recognizable, or could it be?
Awarded Apr 22 '12 at 12:06
Knapsack problem — NP-complete despite dynamic programming solution?
Awarded Mar 31 '12 at 23:14

Others with this badge