user avatar
user avatar
user avatar
Fraïssé
  • Member for 7 years, 9 months
  • Last seen more than a week ago
  • Ichibankan, 5 Chome-3-12 Ginza, Chuo City, Tokyo, Japan
27 votes
7 answers
5k views

Is there a physical analogy to the Turing Machine?

7 votes
1 answer
4k views

How can I make sense of amortized accounting method?

4 votes
1 answer
4k views

Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?

4 votes
3 answers
6k views

What does it mean for a problem to be both NP hard and coNP hard

4 votes
1 answer
50 views

Reference Request: Overlaps between complexity theory and dynamical systems?

3 votes
1 answer
782 views

How to apply "verification" and "decision" for the SUBSET SUM problem?

3 votes
1 answer
287 views

What is the implication of the sentence: "if any NP complete problem is p time solvable, then all problems in NP are p time solvable"

3 votes
1 answer
271 views

Can someone explain in a simple way what "reducible" mean in complexity theory? [duplicate]

2 votes
1 answer
220 views

Can a language recognized by a NFA be recognized by a push down or Turing machine?

1 vote
2 answers
3k views

If algorithm runs $\theta(n)$ in time T, doubling input size has what effect on time T?

1 vote
1 answer
1k views

Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

1 vote
1 answer
2k views

How do deal with the following situations using Prim's algorithm?

1 vote
1 answer
526 views

How does "language" relate to "problem" in complexity theory? [duplicate]

0 votes
1 answer
367 views

Single Source Shortest Path: What does the weights on the vertex and edges tell you?

0 votes
1 answer
1k views

Hadoop MapReduce Word Counting Example [closed]

0 votes
1 answer
291 views

Unclear about proof for unique MST given graph G with distinct weights

0 votes
1 answer
691 views

Why can no task have a utilization rate greater than one?

0 votes
1 answer
546 views

Please explain linear programming as seen for this load balancing problem

0 votes
2 answers
84 views

In general, does $f(g)$ and $f(h)$ have the same time complexity?

0 votes
1 answer
581 views

Can someone provide an introductory example of a certificate in complexity theory? [duplicate]

0 votes
1 answer
1k views

If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

-1 votes
3 answers
2k views

Does there exist $O(n)$ worst case sorting algorithm for sorting a list of integers?

-2 votes
1 answer
639 views

How do I interpret a binary tree generated using Huffman coding algorithm?