Skip to main content
Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel
  • Member for 6 years, 8 months
  • Last seen this week
  • Paris, France
28 votes
Accepted

Is there an algorithm whose time complexity is between polynomial time and exponential time?

26 votes
Accepted

"partial sorting" algorithms (aka "partitioning")

25 votes
Accepted

Does an algorithm's space complexity include input?

24 votes
Accepted

Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?

22 votes
Accepted

Is SAT an existential question?

21 votes

If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

18 votes
Accepted

Why is proving something is NP-complete useful, and where can I use it?

17 votes

Can anyone give me an instance of 3SAT with exactly one solution?

16 votes

False proofs that look correct

15 votes
Accepted

Can we transfer every DFA to DFAs with start state having no in edge?

15 votes
Accepted

Can every spanning tree result from a depth-first search?

15 votes
Accepted

What are you allowed to move into the big O notation for it to be still correct?

12 votes

How to find the largest power of two divisor of a given integer?

11 votes
Accepted

Count number of non-contiguous occurrences in string

10 votes
Accepted

Correctness of FIPS 186-4 square test algorithm

10 votes
Accepted

Does Either...Or means Exclusive Or or Inclusive Or?

10 votes
Accepted

Proof for boosting success probability of a random algorithm with binary output

10 votes

Algorithm to get any spanning tree not necessarily a minimum spanning tree

9 votes
Accepted

What is a witness string? I unable to understand the concept

9 votes

Prove that every substring closed language L ⊆ {0, 1}* is regular

9 votes
Accepted

Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

8 votes
Accepted

How to show L is non-regular without pumping lemma?

8 votes

Arrow notation?

7 votes

Set theory pertaining to category theory and functional programming

7 votes
Accepted

Generating Isomorphic Graphs

7 votes

Length of a regular expression

7 votes
Accepted

Converting Regex to DFA

6 votes
Accepted

Possible Mistake in Skiena's Algorithm Design Manual

6 votes

Is every non-recursively-enumerable language RE-hard?

6 votes
Accepted

What is the difference between the set containing the empty string and the set containing nothing at all?

1
2 3 4 5
17