advocateofnone's user avatar
advocateofnone's user avatar
advocateofnone's user avatar
advocateofnone
  • Member for 9 years, 2 months
  • Last seen more than a week ago
10 votes
Accepted

Is it possible to get Nth Fibonacci number in sublinear time?

9 votes
Accepted

Can all NP-hard problems be reduced to one another?

9 votes

Is there a known method for constructing a grammar given a finite set of finite strings?

7 votes
Accepted

On graph isomorphism for weighted graphs

6 votes
Accepted

How to compute the sum of this series involving golden ratio, efficiently?

6 votes
Accepted

Show that the Halting problem is reducible to its complement

6 votes

How turing machine can be used as enumerator

5 votes
Accepted

Does a context-free grammar with multiple variables have a "starting" point?

4 votes
Accepted

Tile Problem : Dynamic Programming

4 votes
Accepted

Turing Machines: decidability and bounds checking

4 votes
Accepted

Finding a kernel for d-Bounded degree deletion

3 votes

Value returned by recursive function

3 votes
Accepted

Set of Turing machines $S$ such that any $A \in S$ halts on input the description of any $B \in S$

3 votes
Accepted

Certificate Definition of NL

3 votes

Recommendations for a good (rigorous) text to study Computational Complexity.

3 votes
Accepted

Number of winning combination in Nim

3 votes

Is it possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$

2 votes

Square sub-grid with maximum sum

2 votes

Prove that the set of recursive languages is infinite

2 votes

set with maximum sum consisting of mutually co-prime numbers

2 votes
Accepted

Reccurrence for the game of pile of stones

2 votes

Unrestricted grammar for the language of strings whose length is not $2^n$

2 votes

set of Kolmogorov-random strings is co-re

2 votes
Accepted

Reduction from deciders of the universal to deciders of the empty language

2 votes
Accepted

Are "TM M accepts some string of length greater than 100" and "TM M accepts some string of length at most 100" decidable?

1 vote

Prove n! is fully time constructible

1 vote

A heap based problem

1 vote
Accepted

Why descriptive power of context-free grammar is greater than regular expression?

1 vote
Accepted

What happens after the accept state if there are still letters in the string in a Turing machine?

1 vote

Knapsack with same value