Skip to main content
Computer Science

Nice Question

 Nice Question
Question score of 10 or more. This badge can be awarded multiple times.
Awarded 1956 times.
Applications of model counting
Awarded 2 days ago
Partition problem with distinct integers
Awarded Oct 28 at 15:59
Shor's Algorithm speed
Awarded Oct 23 at 17:23
Polynomial time algorithm for finding a maximal monotone subset
Awarded Oct 12 at 15:12
Given n strings, is one of them a substring of another?
Awarded Aug 21 at 20:46
Can the Kolmogorov complexity of a substring be greater than the string?
Awarded Aug 15 at 19:57
Is there a theory around reverse computing?
Awarded Aug 10 at 5:26
Flow-based vs. Reactive programming paradigms
Awarded Jul 15 at 11:38
Minimal basis for set of binary vectors using XOR
Awarded Jun 30 at 7:09
Implications of Rice's theorem
Awarded Jun 27 at 17:33
What is the difference between turing reductions and many-one reductions?
Awarded Jun 24 at 9:11
Myhill-Nerode style characterization of CFL?
Awarded Jun 12 at 19:37
Complexity of (SAT to 3-SAT) Problem?
Awarded Jun 11 at 19:36
Why is every finite language A ⊆ Σ* regular
Awarded Jun 5 at 7:45
A variant of the halting problem for subsets of Turing machines
Awarded May 26 at 20:09
2D interval scheduling problem
Awarded May 26 at 8:10
Is search a binary heap operation?
Awarded May 20 at 2:55
Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace
Awarded May 15 at 5:20
Given two strings ABC and CBA, find A, B and C
Awarded May 7 at 7:57
Problem of constructing binary sequence with least possible 1s under given constraint
Awarded May 3 at 20:04
Solving the min edge cover using the maximum matching algorithm
Awarded May 3 at 10:47
What are the implications of Homotopy Type Theory?
Awarded May 2 at 19:09
How to construct this generalized xor without needing an extra vector?
Awarded Apr 27 at 7:21
λ -calculus : What is the most efficient in memory representation of functions?
Awarded Mar 29 at 1:05
Complexity of Sorting Integers on a Multitape Turing Machine
Awarded Feb 14 at 18:08
Why do pushdown automata use a stack?
Awarded Feb 12 at 22:35
Convert CFG to PDA
Awarded Feb 11 at 15:12
How strong is a Turing Machine that can't control its head movement?
Awarded Feb 6 at 12:26
What's stopping us from smuggling complexity and uncomputability into standard models of computation?
Awarded Jan 28 at 20:51
Finding all solutions to an integer linear programming (ILP) problem
Awarded Jan 28 at 9:12
Proof of non-regularity, based on the Kolmogorov complexity
Awarded Jan 27 at 7:34
Intuition behind the condition |xy| ≤ p in pumping lemma for regular languages
Awarded Jan 27 at 7:34
Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?
Awarded Jan 19 at 20:55
Is this graph problem NP-hard?
Awarded Jan 12 at 15:15
What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?
Awarded Jan 9 at 21:42
Why is a program operating system dependent?
Awarded Dec 30, 2024 at 11:46
What is the average-case complexity of trial division?
Awarded Dec 30, 2024 at 7:22
What was the first programming language with loop break?
Awarded Dec 28, 2024 at 21:57
Halting problem - one issue that's bothering me
Awarded Dec 26, 2024 at 17:03
Purpose of the IRQ on a 6502
Awarded Dec 4, 2024 at 11:36
Exponential analogue of NC?
Awarded Nov 28, 2024 at 23:24
Finding the two largest of five small integers as quickly as possible
Awarded Nov 27, 2024 at 5:55
Graph find all vertices that are part of a cycle
Awarded Nov 19, 2024 at 19:12
Is the class NP closed under complement?
Awarded Oct 27, 2024 at 13:40
Runtime difference bewteen Union by Rank and Union by Size for union-find
Awarded Oct 22, 2024 at 13:04
DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$
Awarded Oct 7, 2024 at 1:51
Multi-point evaluations of a polynomial mod p
Awarded Oct 5, 2024 at 19:05
Proving that any CF language over a 1 letter alphabet is regular
Awarded Oct 2, 2024 at 7:08
Algorithm: Finding shortest path through a dungeon in a game
Awarded Sep 17, 2024 at 22:51
How does the NegaScout algorithm work?
Awarded Sep 16, 2024 at 18:23
Find a weighted median for unsorted array in linear time
Awarded Sep 15, 2024 at 15:05
Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?
Awarded Sep 11, 2024 at 19:41
Why is static recompilation not possible?
Awarded Sep 1, 2024 at 13:40
A Turing machine with each cell accessed at most $10$ times has an equivalent NFA
Awarded Aug 29, 2024 at 13:15
Are all undecidable/uncomputable problems reducible to the Halting problem? [duplicate]
Awarded Aug 28, 2024 at 13:33
Arbitrary precision integer square root algorithm?
Awarded Aug 23, 2024 at 20:25
Are there any problems in $P$ which we do not know any $P$ algorithms?
Awarded Aug 22, 2024 at 12:01
What is a good algorithm for generating random DFAs?
Awarded Aug 15, 2024 at 0:06
What is so fundamental about polynomial functions that they are used to demarcate the Hardness boundary in NP complexity classes?
Awarded Aug 2, 2024 at 7:40
Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?
Awarded Aug 1, 2024 at 14:13
1
2 3 4 5
…
33