user avatar
user avatar
user avatar
fade2black
  • Member for 5 years, 1 month
  • Last seen this week
  • Tbilisi, Georgia
22 votes
6 answers
2k views

Algorithm to test whether a language specified in algebraic form is context-free

  • 141k
15 votes
1 answer
845 views

Grid covering by rectangles

  • 291
12 votes
4 answers
9k views

How does a nondeterministic Turing machine work?

  • 9,612
10 votes
1 answer
279 views

Is there a dual concept to "Turing Complete" in logic?

  • 486
7 votes
1 answer
133 views

Subsequence of one string but not of others

  • 141k
6 votes
2 answers
958 views

Why is the language of TMs that have some quadratic time bound undecidable?

  • 557
6 votes
1 answer
118 views

Min spanning tree that preserves total weight of original graph

  • 227
5 votes
0 answers
73 views

Network Reconstruction from Flow Function

  • 51
4 votes
1 answer
2k views

Greedy algorithms: Minimum sum number pairing

4 votes
1 answer
213 views

Maximizing number of selected squares in a grid

3 votes
0 answers
625 views

Greedy max k-cut approximation algorithm

  • 151
3 votes
2 answers
186 views

NP-complete language as a result of xoring two PTIME languages

  • 173
3 votes
1 answer
271 views

Examples of problems for each class in $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$

  • 2,220
3 votes
1 answer
876 views

3-SAT and Systems of Nonlinear Modular Equations

  • 115
3 votes
1 answer
127 views

The read tape in the definition of L and NL (logarithmic space) (DLOGSPACE, NLOGSPACE) (sublinear space)

  • 243
2 votes
0 answers
56 views

Given multiple families of sets, select a set from each such that the intersection of selected sets is a correspondence

  • 21
2 votes
1 answer
593 views

Deciding on decidability of a problem and reducing it to halting problem if not decidable

  • 35
2 votes
1 answer
982 views

Prove that $L$ is closed under Kleene star iff $L=NL$

2 votes
1 answer
127 views

Expressing the language of squares as a concatenation of two languages

  • 91
2 votes
3 answers
2k views

Best random permutation employing only one random number

2 votes
2 answers
212 views

Protocols for "almost equality" with one-sided error

1 vote
2 answers
1k views

Proving a factor 2 performance guarantee for a greedy minimum cardinality vertex cover algorithm (Exercise)

1 vote
1 answer
149 views

General approach to randomized algorithm for equality problem

1 vote
1 answer
79 views

Is it always possible to have one part of the reduction?

  • 73
1 vote
2 answers
188 views

Optimal generalized bisection method

  • 111
1 vote
1 answer
414 views

Is deciding whether or not a graph is bipartite in $L$?

  • 173
1 vote
1 answer
57 views

Prove that following graph problem is in $L$

1 vote
1 answer
155 views

Reduce Turing Machine

1 vote
1 answer
172 views

Finding maximum rectangular frame in array of zeros and ones

  • 467
0 votes
1 answer
301 views

A Turing machine going to the right by the first $2 |w|$ steps

  • 173