Skip to main content
M a m a D's user avatar
M a m a D's user avatar
M a m a D's user avatar
M a m a D
  • Member for 10 years, 3 months
  • Last seen this week
  • Iran
19 votes
2 answers
14k views

PTAS definition vs. FPTAS

17 votes
3 answers
6k views

Why not to take the unary representation of numbers in numeric algorithms?

10 votes
1 answer
7k views

What is a partially computable function?

9 votes
2 answers
6k views

Why is Oracle Turing Machine important?

7 votes
1 answer
985 views

Does Church-Turing thesis also apply to artificial intelligence?

5 votes
1 answer
416 views

An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number

4 votes
1 answer
3k views

Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input?

3 votes
1 answer
1k views

What is the exact meaning of a Predicate, decidability and computability?

3 votes
2 answers
492 views

Primitive recursive functions and unbounded quantifiers

3 votes
2 answers
6k views

The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm

2 votes
2 answers
468 views

Is it possible to obtain a total function by composition of partial functions?

2 votes
3 answers
455 views

Does the normal form theorem imply that every partially computabe function is primitive recursive?

2 votes
1 answer
675 views

Converting maximization to minimization in aproximation algorithms

2 votes
3 answers
3k views

Why is it meaningless to say the runtime of an algorithm is at least in the order of n squared?

2 votes
2 answers
2k views

Why half of the medians are greater than the median of medians?

2 votes
1 answer
2k views

(a,b)-tree vs B-tree

2 votes
1 answer
121 views

Solution to a Np-hard problem and its relevance to a dual LP

2 votes
1 answer
10k views

How to solve recurrence T(n) = 2T(n/2) + n/log(n) using substitution method

2 votes
0 answers
308 views

Why Johnson’s algorithm for all pairs shortest paths may create negative cycle?

2 votes
1 answer
1k views

Problem with solving the recurrence $T(n) = 2T(\sqrt n) + \log n$ [duplicate]

1 vote
1 answer
279 views

Generate a unique number for a set of sequences of letters

1 vote
1 answer
134 views

Why every point is in exactly one pair in Well Separated Pair Decomposition(WSPD)

1 vote
2 answers
246 views

Problem with proving the undecidability of REGULAR$_{TM}$

1 vote
1 answer
450 views

Problem with the mapping reduction from $A_{TM}$ to $HALT_{TM}$

1 vote
2 answers
1k views

Why is $\dfrac{1}{2}n^2-3n = \Theta(n^2)$?

1 vote
1 answer
707 views

Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm

1 vote
0 answers
905 views

Why do we count the ceils and floors in recursive functions?

1 vote
0 answers
63 views

Solving a recurrence relation [closed]

1 vote
2 answers
97 views

Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?

1 vote
2 answers
289 views

If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$