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, 5 months
  • Last seen more than a month ago
  • 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
8k views

What is a partially computable function?

9 votes
2 answers
6k views

Why is Oracle Turing Machine important?

7 votes
1 answer
988 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
493 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
470 views

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

2 votes
3 answers
456 views

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

2 votes
1 answer
676 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
123 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
309 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
288 views

Generate a unique number for a set of sequences of letters

1 vote
1 answer
136 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
488 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
713 views

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

1 vote
0 answers
912 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
293 views

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