Computer Science
Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel
  • Member for 5 years, 11 months
  • Last seen this week
  • Paris, France
Profile Activity

433 Answers

Score Activity Newest
2 votes
Accepted

What is the name of the complexity class for the optimization version of co-NP-complete and coNexpTime-complete problems?

2 votes

Finding a solution vs Proving that a solution exists

2 votes

What is the complexity class of counting Yes/No instances of an NP problem?

2 votes

Subgraph Isomorphism Problem NP complete?

2 votes

Context Free Grammar Advantages

2 votes
Accepted

if X is in NP but Y is not in NP then can X be reduced to Y?

2 votes
Accepted

When converting from nfa to dfa, do we always ignore the trap state?

2 votes
Accepted

A graph is strongly connected iff every non-trivial cut contains an edge

2 votes
Accepted

Why solving #2SAT in polynomial time implies P = NP?

2 votes

A (False) Proof That ℙ≠ℕℙ

2 votes
Accepted

Is there an efficient way to solve this problem?

2 votes
Accepted

Randomly generated binary search trees case comparison

2 votes

In NP-hardness, can any category reduce to itself? How can you intuitively explain which categories reduce to the others?

2 votes
Accepted

Why the Following Grammars Are Not in CNF

2 votes

can you find an algorithm for this function?

2 votes

Regular Expression Equality

2 votes

Intersection of CFL and DCFL

2 votes
Accepted

Invariant in Kosaraju's algorithm for SCCs

2 votes

What does arc and chain mean in Ford Fulkerson 1956 paper?

2 votes

Context free language with valid Pumping Lemma use

2 votes
Accepted

Minimizing/Maximizing recursion depth for DFS

2 votes
Accepted

Proving that this matching is stable

2 votes
Accepted

Find a key in a BBST for which sum of values of keys smaller then it - is maximal

2 votes

Prove f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n))

2 votes

What are some algorithms with runtimes that involve a \log{n} term with a negative exponent?

2 votes
Accepted

Why is calling an O(n) time algorithm on each node of a tree O(nlogn) time?

2 votes

What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic?

2 votes

How can I prove the following problem is NP complete?

2 votes
Accepted

If a key in a red-black tree has exactly one child (which isn't null) then it is always red

2 votes

How to design a turing machine for a context-free grammar? what are the steps?

1 2 3
4
5
…
15

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.