User Fraïssé

27 votes

7 answers

5k views

Is there a physical analogy to the Turing Machine?

turing-machines computation-models

asked Dec 3, 2014 at 4:58

7 votes

1 answer

4k views

How can I make sense of amortized accounting method?

asked Nov 9, 2014 at 2:57

4 votes

1 answer

4k views

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

correctness-proof spanning-trees

asked Dec 17, 2014 at 6:49

4 votes

3 answers

6k views

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

complexity-theory intuition

asked Dec 2, 2015 at 4:49

4 votes

1 answer

50 views

Reference Request: Overlaps between complexity theory and dynamical systems?

complexity-theory reference-request discrete-mathematics mathematical-foundations physics

asked Feb 29, 2016 at 2:41

3 votes

1 answer

782 views

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

complexity-theory formal-languages sets

asked Dec 3, 2014 at 2:08

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"

complexity-theory np p-vs-np

asked Dec 3, 2014 at 2:29

3 votes

1 answer

271 views

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

complexity-theory terminology reductions

asked Dec 3, 2014 at 4:11

2 votes

1 answer

220 views

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

formal-languages

asked Dec 15, 2014 at 3:22

1 vote

2 answers

3k views

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

algorithms asymptotics runtime-analysis

asked Dec 16, 2014 at 17:53

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?

data-structures trees binary-trees search-trees balanced-search-trees

asked Dec 16, 2014 at 18:07

1 vote

1 answer

2k views

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

graphs minimum-spanning-tree spanning-trees

asked Nov 9, 2014 at 1:24

1 vote

1 answer

526 views

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

complexity-theory

asked Dec 3, 2014 at 3:18

0 votes

1 answer

367 views

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

graphs shortest-path

asked Nov 23, 2014 at 23:10

0 votes

1 answer

1k views

Hadoop MapReduce Word Counting Example [closed]

algorithms parallel-computing cluster

asked Nov 24, 2014 at 19:42

0 votes

1 answer

291 views

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

graphs proof-techniques spanning-trees

asked Dec 16, 2014 at 21:10

0 votes

1 answer

691 views

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

optimization scheduling

asked Mar 23, 2015 at 6:17

0 votes

1 answer

546 views

Please explain linear programming as seen for this load balancing problem

terminology linear-programming modelling

asked Aug 17, 2015 at 5:47

0 votes

2 answers

84 views

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

asymptotics

asked Dec 15, 2014 at 4:37

0 votes

1 answer

581 views

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

complexity-theory np-complete

asked Dec 3, 2014 at 7:38

0 votes

1 answer

1k views

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

complexity-theory np complexity-classes

asked Nov 12, 2016 at 23:38

-1 votes

3 answers

2k views

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

sorting

asked Dec 12, 2014 at 21:09

-2 votes

1 answer

639 views

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

binary-trees encoding-scheme

asked Nov 27, 2014 at 12:55

Stack Exchange Network

current community

your communities

more stack exchange communities

23 Questions

Is there a physical analogy to the Turing Machine?

How can I make sense of amortized accounting method?

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

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

Reference Request: Overlaps between complexity theory and dynamical systems?

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

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"

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

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

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

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

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

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

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

Hadoop MapReduce Word Counting Example [closed]

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

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

Please explain linear programming as seen for this load balancing problem

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

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

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

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

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